bzoj4870:[Shoi2017]组合数问题
传送门
这个题考虑组合数的实际意义，可以将题意转化为从\(nk\)个数里面选\(m\)个数\((m\%k=r)\)的方案数
这个可以\(dp\)求解
设\(f[i][j]\)表示前\(i\)个数选出\(j\)个数（\(j\)是对于\(k\)取mod后的）的方案数
显然有\(f[i][j]=f[i-1][j]+f[i-1][(j-1+k)\%k]\)
可以发现\(i\)状态之和\(i-1\)状态有关，所以可以矩阵加速转移
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e4+10;
int n,mod,k,r;long long tot,f[100],a[100][100],b[100][100],g[100];
int main(){
read(n),read(mod),read(k),read(r);f[0]=1;
for(rg int i=0;i<k;i++){
a[i][i]++;
if(i==0)a[k-1][i]++;
else a[i-1][i]++;
}
tot=1ll*n*k;
while(tot){
if(tot&1){
memset(g,0,sizeof g);
for(rg int i=0;i<k;i++)
for(rg int j=0;j<k;j++)
(g[i]+=f[j]*a[j][i])%=mod;
memcpy(f,g,sizeof f);
}
memset(b,0,sizeof b);
for(rg int i=0;i<k;i++)
for(rg int j=0;j<k;j++)
for(rg int t=0;t<k;t++)
(b[i][j]+=a[i][t]*a[t][j])%=mod;
memcpy(a,b,sizeof a);tot>>=1;
}
printf("%lld\n",f[r]);
}1、MyBatis一对多查询
2、redis相关问题记录
3、Python面向对象之魔术方法
4、thusc2017
5、使用TinyMCE的小tip(2)-中文字体的添加