Thanks, fixed.

Fixed, thanks

Same question and I agree..

[deleted]

Upd: I have made a proof here

I upsolved this problem with iteration method 237083785, but I can't prove why its convergence speed is fast enough. Nevertheless, following is my solution.

First, we have the game procedure:

1. Thief moves to a leaf, cause staying at a non-leaf vertex won't be better than any leaf in it's subtree

2. Thief stays at the leaf until police reaches a leaf. If thief moves to another leaf during the police move, he could have move there in 1.

3. Police chooses another leaf and go directly to it, because he knows that thief's best move is waiting on a leaf

4. After police reaches the leaf, if not caught, all other leaves are accessible to thief. Thief select a vertex based on the leaf police is at and move there, then return to 1.

We can see from the above procedure that non-leaf vertices are irrelevant after the first step, so for the following discussion, vertices are all leaf.

We denote the expected moves that police catches thief starting from leaf $$$u$$$ by $$$E(u)$$$, denote the probability that thief moves to $$$v$$$ if police is at $$$u$$$ by $$$p(u,v)$$$. Then, thief must distribute $$$p(u,v)$$$ in a way that no matter how police changes his strategy, $$$E(u)$$$ will not be larger. In this case, no matter how police chooses, $$$E(u)$$$ stay the same. Thus for $$$u$$$ and every other leaf $$$v_i$$$, we have

$$$E(u)=dis(u,v_1)+(1-p(u,v_1))E(v_1)=dis(u,v_2)+(1-p(u,v_2))E(v_2) = \dots$$$

We try to solve it by iteration method, which means calculate new $$$E'(u)$$$ by $$$E(u)$$$ in the last round, i.e.

$$$ E'(u)=dis(u,v_1)+(1-p(u,v_1))E(v_1)=dis(u,v_2)+(1-p(u,v_2))E(v_2) = \dots$$$

Then, $$$dis(u,v_i)$$$ and $$$E(v_i)$$$ are all constants, the only variable is $$$p(u,v_i)$$$. Hence, we denote $$$x_i$$$ by $$$p(u,v_i)$$$, and the above equation can be rewritten as

Then we have

For the first step where police starts from $$$s$$$, we have the same conclusion that $$$E(s)$$$ stays the same no matter how police moves. Hence, we can calculate $$$E(s)$$$ by the same equation above.

I try to submit and it says contest is over maybe we have to wait for a while.

No. You are required to find the number of solutions to $$$a_1x_1+a_2x_2+a_3x_3=t$$$ where $$$x_i$$$ are given and $$$a_i$$$ are variables. So the key idea is to fix $$$X=a_1 mod x_3$$$ and $$$Y=a_2 mod x_3$$$ and find the number of solutions for this $$$(X,Y)$$$. Suppose $$$Z=(t-Xx_1-Yx_2)/x_3$$$. Then any solution for this $$$(X,Y)$$$ is of the form $$$(X+t_1x_3,Y+t_2x_3,Z-(t_1x_1+t_2x_2))$$$ where $$$t_1,t_2 \geq 0$$$. Now the number of such pairs $$$(t_1,t_2)$$$ for which $$$t_1x_1+t_2x_2 \leq Z$$$ can be found in $$$O(x_2)$$$ by fixing $$$t_1 mod x_2$$$ using some math giving a total complexity of $$$O(x_2x_3^2)$$$.

Yes. Basically we want to find [x^n](1 / ((1 — x^a1) * (1 — x^a2) * (1 — x^a3))) which is f[N] for f[0] = 1, f[x < 0] = 0 and f[N] = sum of -f[N-i] * [x^i]P(x) for i > 0, P(x) being (1 — x^a1) * (1 — x^a2) * (1 — x^a3). This is due to the ties between linear recurrences and generating functions, for functions of this type the denominator being the reverse of the characteristic polynomial of the recurrence.

ax + by + cz = N as we know, case for K = 1 and K = 2 pretty standard so I won't explain

u can calculate L = LCM(a, b, c)

now I say that I iterate on m = min(x, y, z)

now still m doesn't have very good bounds, but what I can observe is

if u have answer for m, u can calculate answer for m + L, m + 2L, it will come out to be arithmetic progression of a kind, still it will be some casework but this is the outline

so u have to iterate from m = 0 to L — 1 and calculate everything using formulaes

I just handled cases, when x = m, y, z > m, x = m, y = m, z > m and so on

I is simply a matter of doing the math and coding as far as I can see. Do a rotating 2-pointers thing that keeps the edges that will define the height of the water surface while rotating the polygon, then it's a matter of doing whatever integration thing that results from that. There's a part that's integrating cos(x) * a and I hope that the other part isn't that much harder, my intuition says that it might simply be P(x) * cos(x) for a polynomial of low degree P(x).

Done!

Powers of b modulo n work in one of 3 ways:

1. There's some positive k such that b^k = 1 modulo n. This happens when gcd(b, n) == 1

2. There's some positive k such that b^k = 0 modulo n. This happens when b is divisible by all primes that divide n.

3. All other cases, which means that b is divisible by some prime that divides n but not all of them.

For case 2 it's simply what happens when we use a "divisibility test" for 2, 5, 10 and so on in base 10.

For case 1, we must divide the digits of the number in such a way that the coefficient of the digits are the congruent to their own coefficient without the division. What I mean is that a number can be written as sum d[i] * b^i and we must choose the division according to the problem in such a way that c[i] * d[i] = b^i * d[i] modulo n, c[i] being what we end up multiplying the i-th digit with after dividing the number under some rule of the problem. From here I think it'd be good for you to think about how to explain it splitting into two cases: the alternating one and the non-alternating one. But I think it's not hard to see how it works from here. The reason why "we must divide the digits[...]" is because it's trivial to create a counter-example if that doesn't happen and if it does happen it's easy to see that it works.

For case 3, if we divide the number under some rule of the problem then there's an arbitrarily large number x such that c[x] = 1, but that can't happen since c[x] * d[x] = b^x * d[x] modulo n must be true and the only non-negative x that makes b^x = 1 modulo n is 0. So this case is impossible to solve.

dude

why so cringe?

If the problem is to solve $$$a_1 x_1 + a_2 x_2 + ... = b$$$ then you just iterate over parity of $$$x_1, x_2, ...$$$ and then reduce the problem to one where each $$$a_i$$$ is doubled.

We’re looking for a few values (how many Pokémon of each species there is). So let me guess the parity of each of these numbers ($$$2^n$$$ options). Knowing the parity of some $$$x$$$ means writing it as either $$$2x’+0$$$ or $$$2x’+1$$$. I subtract what these 0s and 1s give me and from now I need to set each number of species even. But it’s the same as without parity restriction but with the sum two times smaller. Add memorization cause the number of different sums will be small.