题意：求解——
$$(C^{r}_{nk}+C^{r+k}_{nk}+C^{r+2k}_{nk}+...+C^{r+(n-1)k}_{nk}+...)mod(P)$$
其中$C^{m}_{n}$表示从n中选m个的方案数
保证$1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^{30} − 1$
http://www.lydsy.com/JudgeOnline/problem.php?id=4870
一看r，k很小就很自然地想到矩阵快速幂；
然后枚举nk
一开始打算横着递推，处理出每个C，同时处理C的部分和，然而横着递推有问题；
最后发现竖着递推，直接处理C的部分和非常方便。
S(x,y)表示C(ik+x,y)的和，可以从S((x-1+k)%k，y-1)+S(x,y-1)得出；
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL P,N,K,R;
struct Matrix{
LL _[][];
};
Matrix operator * (Matrix a,Matrix b){
Matrix c;
int i,j,k;
memset(c._,,sizeof(c._));
for(i=;i<;i++)
for(k=;k<;k++)
if(a._[i][k])
for(j=;j<;j++)
if(b._[k][j])
(c._[i][j]+=(a._[i][k]*b._[k][j])%P)%=P;
return c;
}
Matrix x,ret;
void Sqr(LL );
int main()
{
int i;
scanf("%lld%lld%lld%lld",&N,&P,&K,&R);
for(i=;i<K;i++)
x._[(i-+K)%K][i]++,x._[i][i]++;
Sqr(N*K);
printf("%lld\n",ret._[][R]);
return ;
}
void Sqr(LL n){
int i;
for(i=;i<;i++)ret._[i][i]=;
while(n){
if(n&)
ret=ret*x;
n>>=,x=x*x;
}
}
存在的问题：
见到组合数就认为不可能在合理的时间内完成行间递推