这种题推式子不行的话可以考虑组合意义,看成在 \(nk\) 个元素中选的个数模 \(k\)\(r\) 的方案数。

容易写出 \(DP\)\(f(i,j)=f(i-1,j)+f(i-1,j-1)\)

如果考虑矩阵快速幂,转移矩阵应是循环矩阵,可以做到 \(O(K^2\ log(nK))\)

注意到这种 \(DP\) 的转移不依赖与之前的状压,也可以倍增转移,写出来实际和上面一样。和 这题 类似。

转移是个循环卷积,如果用 \(Bluestein\) (暂挖坑) 的话应该可以变成 \(O(K \log(K)\log(nK) )\)

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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
int R,K,m,P;
LL n;
int c[maxn];
void Mul(int a[],int b[]){
for(int i=0;i<=K-1;i++) c[i]=0;
for(int i=0;i<=K-1;i++)
for(int j=0;j<=K-1;j++) (c[(i+j)%K]+=(LL)a[i]*b[j]%P)%=P;
for(int i=0;i<=K-1;i++) a[i]=c[i];
}
int A[maxn],B[maxn];
int main(){
freopen("bzoj4870.in","r",stdin);
freopen("bzoj4870.out","w",stdout);
scanf("%d%d%d%d",&n,&P,&K,&R);
n=n*K;
A[0]++; B[0]++; B[1%K]++;
for(;n;n>>=1,Mul(B,B)) if(n&1) Mul(A,B);
printf("%d\n",A[R]);
return 0;
}