Good but almost impossible xD

Yes it needs division. I read it from Elegia's blog here(in Chinese). I can try to do some explanation.

Basically we are still trying to find the number of permutations of length $$$n$$$ containing at least one cycle whose length is a multiple of $$$p^k$$$ for each $$$p$$$ and $$$k$$$.

With some tough generating function manipulation, we can get the number of permutation of length $$$n$$$ , containing no cycles whose length is a multiple of $$$L$$$. It is $$$\frac{n!(L-1)(2L-1)\cdots(kL-1)}{k!L^k}$$$, where $$$k=\lfloor\frac nL\rfloor$$$. We can get the answer we are seeking easily with this.

Since we are doing everything modulo $$$M-1$$$, we can get answer for each prime power divisor $$$q^t$$$ of $$$M-1$$$ and combine them with Chinese Remainder Theorem. It's almost the same as finding $$$\binom{n}{k}\bmod M-1$$$, just write each number in the form $$$q^a\cdot b$$$, where $$$\gcd (q,b)=1$$$. From here we actually have a $$$O(n\cdot\text{poly}\log)$$$ solution already.

The blog did some further optimizing and analyzing to get complexity $$$O(n\log\log n+\frac{n}{\log n}\log M)$$$ (the latter part comes from factorization of $$$M$$$ I think, because we need to find only prime divisors $$$\le n$$$).

To be honest if this is the intended solution I won't like this problem at all :)

Time complexity is $$$(n/z)^2$$$ summed over all prime powers $$$z$$$. This is less than $$$\sum_{i=1}^n\left(\frac{n}{i}\right)^2$$$ which equals to $$$\frac{n^2\pi^2}6$$$ when $$$n$$$ goes to infinity. Hence it is indeed $$$O(n^2)$$$ . I was told there exists $$$O(n\cdot\text{poly}\log)$$$ solution too.

P.S. It seems the system also let $$$O(n^{2+\epsilon})$$$ solutions pass. The given optimization on modulo is probably needed in this case.

Oh, I misread your question. As for checking, just consider an arbitrary spanning tree, and consider all cycles consisting of exactly one edge that is not in the tree. Every nontrivial cycle can be constructed by 'xor'ing the cycles of the above type. So checking if a graph has a nontrivial cycle is equivalent to checking linear independence of all cycles of the above type. This can be done by union-find.

Actually, there's only less than 400 different vector spaces in $$$Z_2^5$$$，so after some preprocessing, you can do gaussian elimination in $$$O(1)$$$ , and do dp where state is current vector space. It works in $$$O(400n)$$$ .

1e17 fail because 1e17*200 exceeds long long limit

1e16 fail because you can get to points like (1e16,2e16) if t=1e16 and (x,y)=(1e16,1e16)

Actually your solution is wrong. It passed because of weak tests.

Your code will fail on the case:

5 2
1 2
2 3
1 4
4 5
2 5
4 3

Answer should be all zero.

Easier way to solve C: Choose the first k/2 left brackets and the last k/2 right brackets. It's not hard to prove this gives a valid bracket sequence.

Actually, there's only need for 3x FFTs. One only needs to calculate A0*B0 , A1*B1 and (A0+A1)*(B0+B1) to get the answer. Also, more research about precision problems in FFT can be found in a research paper by matthew99 in Chinese.

Maybe we should study your previous problems well, to get a whole look of the style of your problems. Maybe?

You can try like this:

while(true)
    rating++;

But this is not practical or

while(date++)
    SolvedProblemsNumber++;

You know you are a programming competitions addict when you have two totally different choices: to take part in a contest or to watch a football match in LFP. You know you are a programming competitions addict when you get up at midnight in China, after two hours of prgramming, still stay up for another 1 hour to see the verdict!

Well, I think it's very hard, because you don't know what Codeforces computers are like. My teacher has told us that we shouldn't declare arrays like that or something unexpected may happen. If you really want to do so, you can just do this:

vector<vector<char> > c(n);
for(int i=0;i<n;i++)c[i].resize(m);

or

const int maxn=105,maxm=105;
char c[maxn][maxm];