洛谷P1357 Solution

题目链接

题解

(mle 5)的数据范围可以想到状压。构造矩阵(a[i][j])，表示最后(m)个花圃状态(i)到状态(j)的方案数。初始状态dfs求出（暴力枚举状态，检验(1)（C形花圃）的数量是否(le k)）。⭐可以发现矩阵乘法类似于Floyd的过程，枚举中转状态（(k)），(i→k)与(k→j)的方案数相乘后求和，天然具备转移方案数的条件。因为花圃是环形的，进行(n)次操作后，状态应与初始状态相同。矩阵快速幂计算(a^n)，(ans=sumlimits_{i=0}^{2^m-1} a[i][i])（二进制下(i)中(1)的数量(le k)）。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=65,mod=1e9+7;
int a[N][N],tmp[N][N],res[N][N],ok[N],b[10],m,k;
void check()
{
	int x=0,y=0,cx=0,cy=0;
	for(int i=1;i<=m;i++) {x=(x<<1)+b[i]; cx+=b[i];}
	for(int i=2;i<=m+1;i++) {y=(y<<1)+b[i]; cy+=b[i];}
	if(cx>k || cy>k) return;
	a[x][y]=ok[x]=ok[y]=1;
}
void dfs(int x)
{
	if(x>m+1) {check(); return;}
	b[x]=1; dfs(x+1);
	b[x]=0; dfs(x+1);
}
void multi(int x[][N],int y[][N],int n)
{
	memset(tmp,0,sizeof(tmp));
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n;k++) tmp[i][j]=(tmp[i][j]+x[i][k]*y[k][j])%mod;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++) x[i][j]=tmp[i][j];
}
void qpow(int x[][N],int y,int n)
{
	memset(res,0,sizeof(res));
	for(int i=0;i<=n;i++) res[i][i]=1;
	while(y)
	{
		if(y&1) multi(res,x,n);
		multi(x,x,n); y>>=1;
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++) x[i][j]=res[i][j];
}
signed main()
{
	int n,ans=0;
	scanf("%lld%lld%lld",&n,&m,&k);
	dfs(1);
	qpow(a,n,(1<<m)-1);
	for(int i=0;i<(1<<m);i++)
		if(ok[i]) ans=(ans+a[i][i])%mod;
	printf("%lld",ans);
	return 0;
}