Так за квадрат же перемножать можно, k маленькое.

Конкретно в этой задаче вроде бы норм проходит и тупое умножение. Если не грешить лишними %mod.

Но в целом... Это, кстати, типичная практика div2 only контестов. Если в обычных матчах div2 D,E — это что-то более-менее креативное и не слишком реализационное, потому как те же задачи идут в div1 B,C, и там различная ересь просто идейно не вписывается, то в div2 only контестах авторы часто грешат тем, чтобы дать задачу, которая будет, возможно даже, не слишком уж идейной, но будет требовать использование какого-нибудь бора, суф.автомата, не совсем примитивного дерева отрезков, FFT или еще чего-нибудь в этом роде.

Не знаю, хорошо это или плохо, но как-то не в моем вкусе) Хотя, мне-то что, я в div2 в ближайшее время не собираюсь)

Но сегодня вроде бы все решаемо без этого скучного "напишите здесь FFT", так что от меня плюсик авторам, которые со своим первым контестом справились очень даже неплохо)

Можно проще: посчитаем 3 динамики — d1[k][depth], d2[k][depth] и d4[k][depth].
d1 — сколько способов раскрасить, если у нас есть k действий, максимальная глубина depth и 1 квадрат. d4 — тоже самое, но у нас есть 4 квадрата, d2 — есть 2 квадрата.
Каждая из динамик пересчитывается через другие за O(k) => получаем k²logN.
http://mirror.codeforces.com/contest/300/submission/3627397

Должно быть, вы ошиблись в реализации.

Я вот искал inv(a) при помощи алгоритма Евклида и получил TLE :(

UPD: Не, Евклид таки не виноват, я сам дурак :)

Сомневаюсь я, что эти строчки

for(i = n; i > b; i--){
        ll x = i;
        while(a > 0 && x % a == 0){ x /= a; a--;}
        v.pb(x);
    }

сокращают правильно.

Тогда C[n][i] = fact[n]inv(fact[n - i]fact[i]). inv(a) — обратный элемент в кольце по модулю. Так как модуль простой, то ...

А можно поподробнее этот момент?

И не проще ли считать С через факториалы по модулю?

I used Floyd-Warshall which works in O(n^3).

n — k + 2 может оказаться нечетным и при делении теряется 0.5, также при других случаях.

thanks. Now fixed.

Изначально про многочлен не думали (ну я по крайней мере), было решение за 4 степень. Пусть действительно у нас есть такой переход с многочленами, предположим. Тогда в решении за 4 степень что делается — перебирается степень j элемента текущего многочлена, потом перебираются все 4-ки (k1, k2, k3, k4), c учётом порядка, которые в сумме дают j. Коэффициенты при k1, k2, k3, k4 перемножаются и прибавляются к текущему при j, что эквивалентно возведению многочлена в 4 степень. Надеюсь стало понятнее :)

Thank you.

Really great to have the analysis so quickly, btw!

You can read it here, for example. It's based on Euler's theorem.

It's basically splitting power of 4 into two square operations. The first calculates power of 2 on the polynomial, stored into a temporary array, then the second calculated power of 2 on the temporary array.

firstly,we can calc how many times can we divid the square,if two square have the same times of divding,their answers is the same,so we just care about how many times the square can be divided. secondly,we can find the**_ subproblem_** of this problem , if we divide a square into four parts,and we can assigned every part a number(dividing times)__ , for example :a b c d. it means part1 be divided a times , part2 be divided b times ..and so on. we'd better construct the square from small to big. So the dp state is dp[i][j] :the tot number of ways when we are constructing the ith small square , we have draw j times , every step ,the square just become two times bigger. the transion is simple , just enumerate the four parts's draw times respectively , and we got a two size bigger square,when doing transion ,we must use a little optimizatioin see my code here

anyone help me ? thanks a lot

It's hard for me to explain ,but anyway , I will try. First'y we should get lp[i] as the editorial says. and then we should use lp[i] to split all the numbers

	for(int i = 0; i < n; i++) scanf("%d",&a[i]),cnt[a[i]]++,sum+=a[i];
	for(int i = M - 10; i >= 2; i--) cnt[i] += cnt[i+1];
	for(int i = M - 10; i >= 2; i--)
	{
		if(lp[i]!=i) cnt[lp[i]] += cnt[i];
		cnt[i/lp[i]] += cnt[i];
	}

cnt[i] is the times prime factor i appear , initially cnt[i] is the numbers bigger than i , so cnt[lp[i]] += cnt[i] and cnt[lp[lp[i]]] += cnt[i].. and so on. but the way of the code above is faster and clever .

Fermat's little theorem. We know that a^(MOD-1)=1 modulo MOD. By definition, inv(a)=a^(-1) and multiplying by a^(MOD-2) gives inv(a)=a^(MOD-2). (The equalities are in fact congruences.)

Note that this is only valid for coprime a and MOD.

Have a look at this article too...

http://en.wikipedia.org/wiki/Euler's_theorem

the fermat's theorem is a case of euler's theorem, with the totient function being equal to (p-1), where p is prime.. i hope it satisfies u...

you can solve with permutations, but its a different type of permutation, see this link

No. I've checked all the TCs now and they are all <=1e6. Can you tell which TC exactly crosses this limit?