CF1152F Neko Rules the Catniverse（状压 DP）

CF1152F Neko Rules the Catniverse

给定参数 n,k,m，你需要求有多少个大小为 k 的序列 a 满足如下三个条件：

1. 任意两个元素其权值不同。
2. 对于任意 i 满足 1≤i≤k 有 1≤ai≤n。
3. 对于任意 i 满足 2≤i≤k 有 ai≤ai−1+m。

答案对 109+7 取模。

1≤n≤109，1≤k≤min(n,12)，1≤m≤4。

一眼根本没有思路，即使知道是状压也不知道如何设状态。。

★Hint：按照位置信息的 DP 走不通，发现题目所给的是关于值域上的限制，考虑根据值域 DP。

状态怎么假设？由于有 n 总范围的限制，需要一个最大值 i。总共需要放置 k 个数，那么需要记录已经放置的数的个数。转移的时候，放入新的数 i，可以放在 ≥i−m 的数的后面或者最开头的位置，所以要记录 ≥i−m 的数有哪些已经出现过了。

这样就合理推出了 DP 状态：fi,j,s 表示当前放置最大值为 i，已经在 [1,i] 中选择了 j 个放在数列中，其中 ≥i−m 的数的选择情况为 s。

转移分为 i+1 选择或不选择两种情况：

• 选择 i+1：

  fi+1,j+1,(2×s)&All|1←fi,j,s×(popcount(s)+1)

• 不选择 i+1：

  fi+1,j,(2×s)&All←fi,j,s

且上面的转移方程可以写成矩阵的形式，边长为 k×2m，则总复杂度为 O(k38mlogn)。

#define Maxsta 208
#define mod 1000000007
int n,K,m,lim,All,pr;
struct Matrix
{
	int f[Maxsta][Maxsta];
	Matrix(){ memset(f,0,sizeof(f)); }
	inline Matrix friend operator * (Matrix x,Matrix y)
	{
		Matrix ret;
		for(int i=0;ifor(int j=0;jfor(int k=0;k
			ret.f[i][j]=(ret.f[i][j]+1ll*x.f[i][k]*y.f[k][j]%mod)%mod;
		return ret;
	}
	inline Matrix friend operator + (Matrix x,Matrix y)
	{
		Matrix ret;
		for(int j=0;jfor(int k=0;k
			ret.f[0][j]=(ret.f[0][j]+1ll*x.f[0][k]*y.f[k][j]%mod)%mod;
		return ret;
	}
};
Matrix trans,ans;
int main()
{
	n=rd(),K=rd(),m=rd(),All=1<1)*All;
	ans.f[0][0]=1;
	for(int j=0;j<=K;j++) for(int s=0;s
	{
		int cur=j*All+s,nex;
		if(j
		{
			nex=(j+1)*All+(((s<<1)&(All-1))|1);
			trans.f[cur][nex]=__builtin_popcount(s)+1;
		}
		nex=j*All+((s<<1)&(All-1));
		trans.f[cur][nex]=1;
	}
	for(;n;n>>=1,trans=trans*trans) if(n&1) ans=ans+trans;
	for(int s=0;s0][K*All+s])%mod;
	printf("%d\n",pr);
	return 0;
}