You can write comment in THIS BLOG, MikeMirzayanov has noticed the issue

I was registered out of competition and had to re-register. I am not sure if everybody noticed that — is there a way to automatically transfer all out-of-comp candidate masters to normal registration?

keep faith in bhai ka swag , Ashishgup he will not disappoint u .

The problem setter's handle has letter '_' in it. This won't be a good contests.

why so ?

I hope someone with the handle name "System_test_failed" reply to this comment

Let's hope your code will pass in system testing too. :)

Any categorization of people according to their respective nationalities is potentially provocative.

excited*
learn to speak English before trying to look smart online.

Anyway it doesn't matter, You won't be busy hitting colours at 9:05pm (IST) in the night.

Yes, it has most of it, but you need to download and launch Topcoder Arena

Your own comment: https://mirror.codeforces.com/blog/entry/66067?#comment-500584 Contradicts the above comment!

So many girls in your expectations.

Because it needs to consider the time in Russia and the time in the author's country. It is late for Chinese students sometimes, but whether you participate in it or not still depends on you. You can balance your study, sleep and the training and the contests. If you really want to join the contest, just do it. If you are worried about the time and will not join it, you still can virtual participate or just practice the problems when you are free.

Ashishgup's contests run smoothly.

Hope for this contest too.

i think pretests should be strong but they should not be too strong otherwise hacking phase will have no meaning !!!

You're a racist.

Who know, who know)

Are you from another dimension, where div.2 easier than div.3?

Codechef

What about Firefox? Is the extension working there?

it just prank bro

I think you have not taken care of adding 10^9+7 while subtracting and then taking mod.

you might be doing (total-calculated_value)%mod, which gave WA to me , but using (((total-calcualted_value)%mod )+mod)%mod which gave AC,hope it may help.

+1

You can always try m1.codeforces.com

zh_zhumash xD

I think your solution was wrong.

for each number g you have to find 3 things:

a = how many numbers are relatively prime to g within range [1,m]

b = how many numbers will have gcd g again when paired with g within range [1,m]

c = how many numbers have gcd<g when paired with g. (This was the hardest part for me in this problem)

The rest is calculating E(g) with a bit of knowledge of probability

My code: 51649595

No need to count connectivity of red edges. Merge all nodes with red edges to components and multiply each member count of adjacent components

Just a linear time solution. O(n)

Count the number of bad strings, and subtract them from total (n^k) to get the final answer.

Think how you can form a bad string, which doesn't traverse through any of the black edges. For simplicity remove the black edges from the graph and then, you'll get some connected components.

To Form a Bad string of length K, all the nodes should be from the same component. If you take nodes from different components, they must have to traverse through a black edge and hence it will not remain a "bad string".

Now suppose cnt = no. of nodes in a connected component. Then no. of bad strings formed by nodes of that particular connected component is = cnt^k

Total no. of bad strings = sum of bad strings of each component.

Note : If the difference is less than 0 after taking modulus with 1e9+7, Add 1e9+7 to make it positive.

and a minute for me for 3 fail hacks

First, notice that this is an inclusion-exclusion type of problem. So the answer will be something like: all possible permutations — all impossible ones. After realizing that, you'll soon notice that all the impossible ones are the collection of nodes that don't have any black edge at all.

Hence, we can simply isolate collection of nodes by using disjoint set. Simply merge when the edge is red and skip the black edge. When you have got a bunch of disjoint sets, you can calculate how many permutations can be constructed from a disjoint set of size x. pow(x, k)

The total answer would be pow(k, n) — (for each disjoint set of size x, pow(x, k))

Solution

lets do tree with only RED . we have forest and answer is n ** k — a1 ** k — .. — af ** k, whee ai number of vertexes in i tree

Count how many sequences are bad (not good) and subtract it from N^K. If we make the graph only with red edges, for each connected component with size X we will get X^K bad sequences from this component. Sum of bad sequences for each component will give total number of bad sequences. It's not possible to get any more bad sequence because merging any two component would need black edge which we can't use in bad sequences.

You can solve it in a single iteration from n-1 to 0, making it O(n).
Check my simple solution.

Think greedy.
Use the maximum possible number of chocolates from a_n and with considering the picks use the maximum possible number of chocolates from a_n-1 and so on...

How so?

In fact, it can be solved by just dfs.

You need a newline at the end of the input.

My solution was calculating the probability of obtaining an array of length n with the gcd of the array(except the last elemnent) as x with ending element y where $$$x,y \in [1,m]$$$, $$$ n \in [1,\inf]$$$ and y is coprime to x.
Then, summed up the contributions with a bit of math.

0 is non-negative and 0 is smaller than 4.

0 is a non-negative integer. The MEX of {1,2,3} is 0, because 0 is not in the set. It would be 4 if the set was {0,1,2,3}.

EDIT: Triple ninja-d :) Because 0 is nonnegative?

non-negative integer means zero is included.
{0,1,2,3,...}

Oh thanks, I'm sleepy :D

I think the answer is just $$$n^k-\sum p^k \pmod{1e9+7}$$$

Yes. I used Kuhn's Algorithm

Yes. But there is tricky part, it is not just reduction to maximal matching problem.

I have the same thoughts about C and D))

why ?

The first one will be ignored and you will get penalty of -50 for re-submission.

Because servers are now upgraded and with compiler optimizations almost around O(10^9) passes in one sec.

Probably compiler optimization.

The compiler optimizes the increments in the for loop into an addition. After optimization, the complexity is $$$O(n)$$$.

See my solution: https://mirror.codeforces.com/blog/entry/66067?#comment-500828

No. of N-length arrays: Sum(C[i] ^ N) / m ^ N. ( 1 <= N <= ...)
C[i]: Count of multiples of C[i] <= m. (Make sure that we do not re-count multiples, C[x] -= C[y])
If you re-arrange 1st statement, you can get sum of infinite GPs for each C[i].
Sum the answer for all C[i].

Because you count something twice or more. Let call the first expression is f(q), then you want f(i) is the answer with some first element have gcd() = i, but you also count the other with gcd = 2i, 3i, ... So you need to subtract f(2i), f(3i) to get the right answer.

Actually, what you're looking for is $$$\sum_{i=1}^{\infty} (i+1)*q^i*(1-q)=\frac{q*(2-q)}{1-q}$$$(you need to factor out the $$$1-q$$$ for wolfram alpha to give you the result: https://www.wolframalpha.com/input/?i=(sum+of+i+from+1+to+inf+(i%2B1)*a%5Ei)*(1-a)*1 . Make sure to add $$$\frac{1}{m}$$$ at the end for the special case of length 1. AC code: 51651931

I had the same misconception in the beginning, couldn't thing of anything better than O(N^2).

Same happened to me. Lost a lot of time for not reading again the problem statement.

Couldn't solve it because I understood the same.. After almost 2 hours thinking i'm pretty sure there isn't anything better than N^2.

It's magic of GNU C++

Maybe compiler optimization

for (int j = 0; j <= i; j++){
     ans++;
}

The above block is optimized to ans += i + 1; you can see that here.

compiler optimization + server upgrades !!!

I think if we use Hopcroft Karp we need to binary search on the answer and so we attain complexity of $$$O(N^2 \cdot sqrtN \cdot logN)$$$. Can you explain your approach of using Hopcroft Karp and attaining complexity $$$O(N^2 \cdot sqrtN)$$$?.