题面：
思路：
把P形花圃记录为0，C形记录为1，那么一段花圃就可以状态压缩成一个整数
那么，我们可以有这样的状压dp：
dp[i][S]表示前i个花圃，最后m个的状态为S的情况
如果这是一条链的花圃，那么直接状压转移就可以了，但是这道题是一个环
一个环上，前m-1个花圃会影响到后m-1个花圃的状态
因此我们考虑把这个环后面再“长出”m个花圃来，消除这种影响
具体做法是：
枚举所有合法的状态S，令dp[1][S]=1，其余为零，代表前m个的状态确定了然后递推
最后把dp[n+1][S]加入答案，代表最后m个（第1～0-m+1个）的状态为S
由于n比较大，因此需要预处理出转移，写成矩阵快速幂的形式（因为这里的递推显然是线性的）
Code：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define mx 1e16 6 #define ll long long 7 using namespace std; 8 inline ll read(){ 9 ll re=0,flag=1;char ch=getchar(); 10 while(ch>'9'||ch<'0'){ 11 if(ch=='-') flag=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar(); 15 return re*flag; 16 } 17 ll n,m,K,MOD=1e9+7; 18 struct ma{ 19 ll a[50][50],n,m; 20 ma(){memset(a,0,sizeof(a));n=m=0;} 21 void clear(){memset(a,0,sizeof(a));n=m=0;} 22 const ma operator *(const ma &b){ 23 ma re;re.n=n;re.m=b.m;ll i,j,k; 24 for(i=1;i<=n;i++){ 25 for(j=1;j<=b.m;j++){ 26 for(k=1;k<=m;k++){ 27 re.a[i][j]+=a[i][k]*b.a[k][j]; 28 re.a[i][j]%=MOD; 29 } 30 } 31 } 32 return re; 33 } 34 const void operator =(const ma &b){ 35 n=b.n;m=b.m;ll i,j; 36 for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]=b.a[i][j]; 37 } 38 }A,B,ans; 39 ll st[50],cnt,in[50]; 40 ll count(ll x){ 41 ll re=0; 42 while(x){ 43 if(x&1) re++; 44 x>>=1; 45 } 46 return re; 47 } 48 ma ppow(ma x,ma y,ll t){ 49 while(t){ 50 if(t&1) x=x*y; 51 y=y*y;t>>=1; 52 } 53 return x; 54 } 55 int main(){ 56 n=read();m=read();K=read(); 57 ll i,t1,t2,j; 58 for(i=0;i<(1<<m);i++){ 59 if(count(i)<=K) st[++cnt]=i,in[i]=cnt; 60 } 61 A.n=1;A.m=B.n=B.m=cnt; 62 for(i=1;i<=cnt;i++){ 63 t1=(st[i]<<1)&((1<<m)-1);t2=t1+1; 64 if(in[t1]) B.a[i][in[t1]]=1; 65 if(in[t2]) B.a[i][in[t2]]=1; 66 } 67 ll re=0; 68 for(i=1;i<=cnt;i++){ 69 A.clear();A.a[1][i]=1;A.n=1;A.m=cnt; 70 ans=ppow(A,B,n); 71 re+=ans.a[1][i];re%=MOD; 72 } 73 printf("%lld",re%MOD); 74 }