大傻逼题……就是求 (nk) 个元素选出一些元素,选出的元素的个数要满足模 (k) 余 (r),求方案数。
想到 (inom{n}{m}=inom{n-1}{m-1}+inom{n-1}{m}),递推取模就是了……
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, p, k, r;
struct Matrix{
int num[55][55];
Matrix operator*(const Matrix &x)const{
Matrix re;
for(int i=0; i<k; i++)
for(int j=0; j<k; j++){
re.num[i][j] = 0;
for(int l=0; l<k; l++)
re.num[i][j] = (re.num[i][j] + (ll)num[i][l]*x.num[l][j]) % p;
}
return re;
}
}dan, zhu, yua;
Matrix ksm(ll b){
while(b){
if(b&1) dan = dan * zhu;
zhu = zhu * zhu;
b >>= 1;
}
return dan;
}
int main(){
cin>>n>>p>>k>>r;
for(int i=0; i<k; i++){
dan.num[i][i] = zhu.num[i][i] = 1;
zhu.num[(i-1+k)%k][i]++;
}
yua.num[0][0] = 1;
cout<<(yua*ksm((ll)n*k)).num[0][r]<<endl;
return 0;
}