4870: [Shoi2017]组合数问题
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 829 Solved: 446
[Submit][Status][Discuss]
Description
Input
第一行有四个整数 n, p, k, r，所有整数含义见问题描述。
1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1
Output
一行一个整数代表答案。
Sample Input
2 10007 2 0
Sample Output
8
HINT
注意到问题就是求从n*k件物品中选出若干件使得选出的物品的数量%K=R的不同方案个数,f[i][j]表示从前i件物品中选出若干件满足选出物品的数量%K=j的方案个数，有f[i][j]=f[i-1][j]+f[i-1][((j-1)+K)%K],显然利用矩阵幂可以快速转移，注意特判下K=1的情况。由于快速幂传参写的是int，但是N*K可能爆int一直WA最后才发现= =
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<stack>
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<time.h>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define debug puts("debug")
#define LL long long
#define ULL unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define eps 1e-10
#define inf 0x3f3f3f3f LL N,P,K,R;
LL qpow(LL a,LL b,LL p){
LL r=;
while(b){
if(b&) r=r*a%p;
a=a*a%p;
b>>=;
}
return r;
}
struct matrix{
LL a[][];
matrix(){
memset(a,,sizeof(a));
}
matrix operator*(matrix& tmp){
matrix ans;
for(int i=;i<K;++i){
for(int j=;j<K;++j){
for(int k=;k<K;++k){
(ans.a[i][k]+=a[i][j]*tmp.a[j][k])%=P;
}
}
}
return ans;
}
}A,I;
matrix qpow(matrix X,LL n){
matrix ans=I;
while(n){
if(n&) ans=ans*X;
X=X*X;
n>>=;
}
return ans;
}
int main(){ scanf("%lld%lld%lld%lld",&N,&P,&K,&R);
N*=K;
if(K==){
printf("%lld\n",qpow(,N,P));
}
else{
for(int i=;i<K;++i) I.a[i][i]=;
A.a[][]=A.a[][K-]=;
for(int i=;i<K;++i){
A.a[i][i]=A.a[i][i-]=;
}
matrix ans=qpow(A,N);
printf("%lld\n",ans.a[R][]);
}
return ;
}