BZOJ4870 - Click Here
Description
Input
第一行有四个整数 n, p, k, r，所有整数含义见问题描述。
1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30-1
Output
一行一个整数代表答案。
Solutions
注意到数据范围$r<k$，因此此题实质上是求$\sum \binom{i}{j}, \, j\equiv r(mod \, k)$
尝试推一推式子，由于$i,j>0$，根据对称恒等式有
$\sum \binom{i}{j}=\sum (\binom{i-1}{j}+\binom{i-1}{j-1})=\sum \binom{i-1}{j}+\sum \binom{i-1}{j-1}, \, j \equiv r(mod \, k)$
由于$j \equiv r(mod\, k)$，所以$(j+k-1) \equiv (r+k-1) \, (mod\, k)$
也就是说，我们并不关心$\binom{i}{j}$是多少，只关心$\sum \binom{i}{j}, \, j\equiv r(mod\, k)$，包括推导过程。
因此，可以得到一个dp方程，用$f(i,j)$表示$\sum \binom{i}{j}, \, j \equiv r(mod \, k)$
然后易得转移方程$f(i,j)=f(i-1,j)+f(i-1,(j+k-1)\, mod \, k)$
线性递推式，矩阵乘幂优化一下就好了。
时间复杂度$O(k^3log\,nk)$
P.S. 网上的主流做法，是将组合数看做取小球问题，然后直接得到转移方程。QAQ
CODE
CODE - Click Here