Problem Detail: This is a problem from a past contest at topcoder : Problem. Its solution is given here : Solution [Scroll Down to Penguin Emperor] I am unable to understand how the section with subheading “Combinations are associative” works. What is actually going on in this step ? How is the convolution property being used ? Or the Associative property of Combination ? How is the exponentiation squaring being performed ? EDIT Problem Statement You are Given N cities numbered from 0 to N-1 in a circular order. You are currently at city index 0. On first day you can move from your your current city with index i to a city with index j such that
j = (i+N-1)MOD N or j = (i+1)MOD N
On second day you can move from your your current city with index i to a city with index j such that
j = (i+N-2)MOD N or j = (i+2)MOD N
and so on. So on Day x, you can move from your your current city with index i to a city with index j such that
j = (i+N-(X MOD N))MOD N or j = (i+(X MOD N))MOD N
You have to travel on each day. Given the number of Days M, find the total number of ways, you can travel starting from city index 0 such that at the end of M days you are back to city index 0 , modulo 1000000007. The solution given is as following :
final int MOD = 1000000007; // Discrete convolution: int[] combine(int[] A, int[] B) { int n = A.length; int[] C = new int[n]; // Skipping when B[i] = 0, is a key optimization: for (int i=0; i<n; i++) if (B[i] != 0) { for (int j=0; j<n; j++) { int k = (j - i + n) % n; C[k] += (int)( (A[j]*(long)B[i]) % MOD ); if (C[k] >= MOD) { C[k] -= MOD; } } } return C; } // Exponentiation by squaring, for our convolution operation: int[] power(int[] A, long x) { int n = A.length; int[] R = new int[n]; R[0] = 1; while (x > 0) { if ( (x & 1) != 0) { R = combine(R, A); } A = combine(A, A); x >>= 1; } return R; } public int countJourneys(int numCities, long daysPassed) { // Generate R and Q: int[] Q; int[] R = new int[numCities]; R[0] = 1; Q = R; for (int i=1; i<=numCities; i++) { //B holds T[i] int[] B = new int[numCities]; B[i % numCities] = 1; B[numCities - i] = 1; R = combine(R, B); if (i == daysPassed % numCities) { Q = R; } } R = power(R, daysPassed / numCities); R = combine(R, Q); return R[0]; } countJourneys(N, M) is called to get the answer.
Asked By : Kyuubi
Answered By : Yuval Filmus
The idea is to use dynamic programming. For each day $k$, we find the number of ways (modulo $p = 1000000007$) to get from $0$ to $x$ for each $x in {1,ldots,N}$. Given the array $A_k$ for day $k$, the array $A_{k+1}$ for day $k+1$ is given by $$ A_{k+1}(x) = A_k(x-k-1) + A_k(x+k+1), $$ where all indices are modulo $N$. The actual computation is done modulo $p$. In your case, it seems that $M gg N$, and then this method is a bit slow. That’s why we want to use convolution. There is another way to describe the calculation above. Consider formal variables $x_0,ldots,x_{N-1}$ that satisfy the rule $x_i x_j = x_{i+j pmod{N}}$ (for concreteness, we could take $x_j = e^{2pi i (j/N)}$; but we could also just treat them as formal variables.) We represent the array $A_k$ in the form $$ A_k = sum_{i=0}^{N-1} A_k(i) x_i. $$ We have $A_0 = x_0$ and $A_{k+1} = (x_{k+1} + x_{-k-1}) A_k$ (all indices modulo $N$). This kind of multiplication is known as convolution, and it satisfies all the usual rules of multiplication (it is commutative and associative). When $M$ is big, we want to take advantage of the fact that $A_k = A_{k pmod{N}}$. So $$ A_k = prod_{i=1}^N (x_i + x_{-i})^{lceil (k-i+1)/N rceil} A_0. $$ The idea now is to compute $(x_i + x_{-i})^d$ using repeated squaring, which you can look up. For example, to compute $X^{10}$ we would compute $X,X^2,X^4,X^8$ and multiply $X^2$ and $X^8$ (more generally, we look at the binary expansion of the exponent). Given all the factors, we multiply everything together and then look at the coefficient of $x_0$. Since we only want the result modulo $p$, we do all the computations modulo $p$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13039
