【数据规模】
40%的数据中，N<=20；
60%的数据中，M=2；
80%的数据中，N<=10^5。
100%的数据中，N<=10^15。
看到这个数据范围，我首先想到的是80分的写法
80分的写法可以使用状压DP
f[i][j]表示第i位，前m个二进制状态为j有多少种方式
t1=(j>>1)|(1<<(m-1));
t2=j>>1;
转移到下一位有两种选择
t1为选C花圃，t2为选P花圃
当然如果选t1则超过k个C花圃，则不可转移
if(ji[t1]<=k) f[i+1][t1]=(f[i+1][t1]+f[i][j])%mo; f[i+1][t2]=(f[i+1][t2]+f[i][j])%mo;
另外要注意的是原花圃是一个环
所以我们枚举起始状态，转移n+m次，取f[n+m]中状态与起始相同加入总和
80分的状压DP具体实现如下：
#include <algorithm> #include <iostream> #include <cmath> #include <cstring> #include <map> #include <string> #include <vector> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> using namespace std; typedef long long ll; inline ll read() { register ll p(1),a(0);register char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') p=-1,ch=getchar(); while(ch>='0'&&ch<='9') a=a*10+ch-48,ch=getchar(); return a*p; } const ll N=100100,M=(1<<5),mo=1000000007; ll f[N][M],n; int ans=0,ji[M],t1,t2,m,k; inline int suan(int xx) { register int num=0; while(xx) { if(xx&1) num++; xx>>=1; } return num; } int main() { // freopen("input","r",stdin); // freopen("output","w",stdout); n=read(),m=read(),k=read(); for(register int i=(1<<m)-1;i>=0;i--) ji[i]=suan(i); for(register int kk=(1<<m)-1;kk>=0;kk--) if(ji[kk]<=k) { memset(f,0,sizeof(f)); f[m][kk]=1; for(register int i=m;i< n+m;i++) for(register int j=(1<<m)-1;j>=0;j--) { t1=(j>>1)|(1<<(m-1)); t2=j>>1; // prllf("%d %d ",t1,t2); if(ji[t1]<=k) f[i+1][t1]=(f[i+1][t1]+f[i][j])%mo; f[i+1][t2]=(f[i+1][t2]+f[i][j])%mo; } ans=(ans+f[n+m][kk])%mo; } printf("%d",ans); return 0; }
然后我们再来考虑100分的做法
范围开到了1e15我们显然只能使用logn的算法
很容易想到矩阵快速幂的套路
使用状压DP的2^m种状态作为点
于是可以使用原来的思路建出一步可达矩阵图
快速幂n次方即可
100分矩阵快速幂实现如下：
#include <algorithm> #include <iostream> #include <cmath> #include <cstring> #include <map> #include <string> #include <vector> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> using namespace std; typedef long long ll; inline ll read() { register ll p(1),a(0);register char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') p=-1,ch=getchar(); while(ch>='0'&&ch<='9') a=a*10+ch-48,ch=getchar(); return a*p; } const ll N=100100,M=(1<<5),mo=1000000007; struct matrix { ll data[M][M]; matrix(){memset(data,0,sizeof(data));} }; ll f[N][M],n,ans=0,ji[M],t1,t2,m,k,big; inline int suan(int xx) { register int num=0; while(xx) { if(xx&1) num++; xx>>=1; } return num; } matrix chen(matrix a,matrix b) { matrix c; for(register int i=0;i<big;i++) for(register int j=0;j<big;j++) if(a.data[i][j]) for(register int k=0;k<big;k++) c.data[i][k]=(c.data[i][k]+a.data[i][j]*b.data[j][k])%mo; return c; } matrix qs(matrix a,ll b) { matrix ans; for(register int i=0;i<big;i++) ans.data[i][i]=1; while(b) { if(b&1) ans=chen(ans,a); a=chen(a,a); b>>=1; } return ans; } int main() { // freopen("input","r",stdin); // freopen("output","w",stdout); n=read(),m=read(),k=read(); matrix temp,now; big=1<<m; for(register int i=(1<<m)-1;i>=0;i--) ji[i]=suan(i); for(register int i=(1<<m)-1;i>=0;i--) if(ji[i]<=k) { t1=(i>>1)|(1<<(m-1)); t2=i>>1; if(ji[t1]<=k) temp.data[i][t1]=1; temp.data[i][t2]=1; } temp=qs(temp,n); for(register int i=(1<<m)-1;i>=0;i--) if(ji[i]<=k) ans=(ans+temp.data[i][i])%mo; printf("%lld",ans); return 0; }