BZOJ4870
。。估计大多数人都是看题推式子。。然后各种码逆元。。
CRT
。。
Lucas
定理等奇奇怪怪的东西。。然后还发现拿不了满分。。
最后看到题解，就各种憋住的**破口而出。。 其实题目就是求
nk
个数中，取得的数模
k
为r的方案数。。 显然有
fi,j=fi−1,j−1+fi−1,j
(
fi,0=fi−1,0+fi−1,k−1
) 这，这
TM
矩阵乘法优化一下不就好了！！？
【代码】
using namespace std;
typedef long long ll;
ll
read()
{
ll
x=
0,f=
1;char ch=getchar();
while(!isdigit(ch)){
if(ch==
'-') f=-
1;ch=getchar();}
while(isdigit(ch)){
x=(
x<<
1)+(
x<<
3)+ch-
'0';ch=getchar();}
return x*f;
}
int n,Mod,k,r;
class Matrix{
public:
int v[
55][
55];
int x,
y;
}a,b;
Matrix operator
*(Matrix A,Matrix B){
Matrix rtn;rtn.
x=A.
x,rtn.
y=B.
y;
for(
int i=
1;i<=A.
x;i++)
for(
int j=
1;j<=B.
y;j++)
{
rtn.v[i][j]=
0;
for(
int k=
1;k<=A.
y;k++)
rtn.v[i][j]=(rtn.v[i][j]+
1LL
*A.v[i][k]
*B.v[k][j]
%Mod)
%Mod;
}
return rtn;
}
Matrix Qpow(Matrix X,ll Y)
{
Matrix rtn;rtn.
x=rtn.
y=k;
for(
int i=
1;i<=k;i++)
for(
int j=
1;j<=k;j++) rtn.v[i][j]=(i==j)?
1:
0;
while(Y) {
if(Y&
1) rtn=rtn
*X;
X=X
*X;Y>>=
1;
}
return rtn;
}
int Ksm(
int x,ll
y){
int rtn=
1;
while(
y) {
if(
y&
1) rtn=
1LL
*x*rtn%Mod;
x=
1LL
*x*x%Mod;
y>>=
1;
}
return rtn;
}
int main()
{
n=
read(),Mod=
read(),k=
read(),r=
read();
if(k==
1) {
printf(
"%d\n",Ksm(
2,n));
return 0;
}
a.v[
1][
1]=
1;a.
x=
1,a.
y=b.
x=b.
y=k;
for(
int i=
1;i<=k;i++)
{
b.v[i][i]=
1;
if(i!=
1) b.v[i][i-
1]=
1;
else b.v[i][k]=
1;
}
b=Qpow(b,
1LL
*n*k);
a=a
*b;
printf(
"%d\n",a.v[
1][r+
1]);
return 0;
}
