Description
Data Constraint
Solution
其实式子很显然，但就是没看出来。最恐怖的是还没看到r< k 我们可以将式子看成在n*k个球中挑选x个球的方案数，满足x%k=r。那么显然是设f[i][j]表示前i个球中取的球modk=j的方案数。f[i][j]=f[i-1][j]+f[i-1][j-1]，矩阵乘法一下即可。
Code
using namespace std;
const
int maxn=
55;
ll n,p,k,r,i,t,j,l,
x,
y,z,d[maxn];
struct code{
ll a[maxn][maxn];
code friend operator * (code
x,code
y){
code z;memset(z.a,
0,sizeof(z.a));
int i,j,k;
for (i=
0;i<=
50;i++)
for (j=
0;j<=
50;j++)
for (k=
0;k<=
50;k++)
z.a[i][j]=(z.a[i][j]+
x.a[i][k]
*y.a[k][j]
%p)
%p;
return z;
}
}c,a,b;
void dg(){
while (n>
1) d[++d[
0]]=n
%2,n/=
2;
a=c;
for (;d[
0];d[
0]--){
a=a
*a;
if (d[d[
0]]) a=a
*c;
}
}
ll mi(ll
x){
if (
x==
1)
return 2;
ll t=mi(
x/
2);
if (
x%2)
return t
*t%p*2%p;
return t
*t%p;
}
int main(){
// freopen(
"data.in",
"r",stdin);
scanf(
"%lld%lld%lld%lld",&n,&p,&k,&r);
c.a[
0][
0]=c.a[k-
1][
0]=
1;
for (i=
1;i<k;i++)
c.a[i][i]=c.a[i-
1][i]=
1;
n
*=k;
if (k>
1){
dg();
b.a[
0][
0]=
1;
b=b
*a;
t=b.a[
0][r];
}
else t=mi(n
*k);
printf(
"%lld\n",t);
}
