题面在这里
考虑实际意义，就是从\(nk\)个中选\(r\)个，选的个数是在模k意义下的
仍旧满足\(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\)
矩乘即可
WA了2发的经历告诉我构造转移矩阵一定不能赋值！！！！
示例程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<cstdio>
#include<cstring>
#define cl(x,y) memset(x,y,sizeof(x))
typedef long long ll;
int n,p,k,r;
struct matrix{
int n,m; ll s[50][50];
matrix () {cl(s,0);n=m=0;}
}t,ans;
inline matrix operator*(const matrix&a,const matrix&b){
matrix c;
c.n=a.n;c.m=b.m;
for (int i=0;i<c.n;i++)
for (int j=0;j<c.m;j++)
for (int k=0;k<a.m;k++)
(c.s[i][j]+=a.s[i][k]*b.s[k][j])%=p;
return c;
}
matrix power(matrix a,ll b){
matrix w=a,res;
res.n=res.m=k; for (int i=0;i<k;i++) res.s[i][i]=1;
while (b){
if (b&1) res=res*w;
w=w*w;
b>>=1;
}
return res;
}
int main(){
scanf("%d%d%d%d",&n,&p,&k,&r);
ans.n=k;ans.m=1; ans.s[0][0]=1;
t.n=t.m=k;
for (int i=0;i<k;i++) t.s[i][i]++,t.s[i][(i-1+k)%k]++;
ans=power(t,(ll)n*k)*ans;
printf("%lld",ans.s[r][0]);
return 0;
}
|
