【DP】BZOJ4870[Shoi2017]组合数问题

分析：

比较简单的DP水题

很显然，$DP(n,i)$表示在n个物品中选出$i+k?x(x\in Z)$个的方案数

$DP(2?n,i)=\sum DP(n,j)?DP(n,i?j)$
可以理解为：前n个数中选j个，后n个数中选i-j个 的方案数

然后就随便倍增啦。。。
类似快速幂的形式

代码比矩乘短到不知道哪里去了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 110
using namespace std;
typedef long long ll;
ll n,p;
int k,r;
ll f[MAXN],f1[MAXN];
void query(ll f[],ll N){
    if(N==1){
    f[0]=1;f[1%k]++;return ;	}query(f,N>>1);memset(f1,0,sizeof f1);for(int i=0;i<k;i++)for(int j=0;j<k;j++)f1[(i+j)%k]=(f1[(i+j)%k]+f[i]*f[j]%p)%p;for(int i=0;i<k;i++)f[i]=f1[i];if(N&1){
    for(int i=0;i<k;i++)f1[i]=(f[i]+f[(i+k-1)%k])%p;for(int i=0;i<k;i++)f[i]=f1[i];}
}
int main(){
    SF("%lld%lld%d%d",&n,&p,&k,&r);query(f,n*k);PF("%lld",f[r]);
}