BZOJ4870 [SHOI2017]组合数问题

题意

求$$\Big(\sum_{i=0}^{\infty}C_{nk}^{ik+r}\Big)mod p$$的值。
其中$1 \leqslant n \leqslant 10^9, 0 \leqslant r < k \leqslant 50,2 \leqslant p \leqslant 2^{30}-1$。

题解

初看这题以为是个推式子题,然后就深陷其中无法自拔了……于是根本没想到正解。
其实看范围应该是可以想到矩阵快速幂的。但是,个人认为……这道题的脑洞还是比较大的,需要考虑式子的组合意义。
在往组合意义的方向思考后,不难发现,这个式子求的是,在$nk$个物品中选出的个数在模$k$意义下为$r$的方案数,于是这个式子便可以轻松$O(nk^2)$来DP了。
然后可以注意到这里可以使用矩阵快速幂加速,于是这道题就可以在$O(k^3log(nk))$的时间内解决了。
啊……这种题连DP都没想到,更别说后面的加速……真的太菜了。

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=50+10;
int mod,n;
struct Matrix{
int Res[maxn][maxn];
Matrix(){
memset(Res,0,sizeof(Res));
}
};
struct Matrix A,B,C;
Matrix operator * (const Matrix &a,const Matrix &b){
Matrix res;
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
res.Res[i][j]=(res.Res[i][j]+1ll*a.Res[i][k]*b.Res[k][j]%mod)%mod;
return res;
}
inline Matrix qpow(Matrix Base,ll power){
Matrix res;
int i;
for(i=1;i<=n;i++)res.Res[i][i]=1;
while(power){
if(power & 1ll)res=res*Base;
Base=Base*Base;
power>>=1ll;
}
return res;
}
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
int i,j,k,m,r;
#ifndef ONLINE_JUDGE
freopen("BZOJ4870.in","r",stdin);
freopen("BZOJ4870.out","w",stdout);
#endif
k=read();mod=read();n=read();r=read();
for(i=1;i<=n;i++){
A.Res[i][i]++;A.Res[i][i%n+1]++;
}
B=qpow(A,1ll*n*k);
C.Res[1][1]=1;C=C*B;
printf("%d\n",C.Res[1][r+1]);
return 0;
}