小编点评

首先，这个问题是一个关于动态规划（DP）和二进制表示的问题。给定了一个长度为n的数列，要求找到一个子序列，使得该子序列中相邻的m个数字（m <= n）满足一定的条件。具体来说，就是这m个数字的二进制表示中没有连续的1。 我们可以将这个问题转化为一个二维DP数组dp[i][j]，其中dp[i][j]表示考虑第i位，从第i-m+1位到第i位的状态，以及当前最长的连续1的长度是否小于等于j。这里，j表示最长的连续1的长度。 对于dp数组的初始化，我们可以先考虑最简单的情况，即m=1的情况。此时，dp[i][0]表示考虑第i位，只有0的情况，显然dp[i][0]=1。对于其他情况，我们可以使用以下转移方程： dp[i][j] = dp[i-1][j] + dp[i-1][j-1] 这个转移方程的意思是，如果第i位之前有连续的1，那么当前位可以是0或1；如果第i位之前没有连续的1，那么当前位只能是1。 在主程序中，我们首先根据题目给定的n、m、K进行初始化，并构建一个转移矩阵t。然后，我们遍历所有可能的连续1的长度k，并根据t矩阵计算出dp[n+m][k]的值。最后，dp[n+m][k]的值即为所求答案。 需要注意的是，这个问题还可以使用更高效的算法，例如使用二分查找和哈希表等数据结构来优化。但是，由于题目要求使用DP算法，并且数据规模不大，因此我们采用了简单的DP算法进行求解。

正文

感觉是道好题，但我用了比较久的时间才贺出来

观察 \(m\) 和 \(k\) 很小，而题目只要求相邻 \(m\) 个满足要求 ，显然直接对 \(m\) 个 0 或 1 状压（后文的数字 1 指的是填 C）。设 \(dp[i][j]\) 表示考虑到第 \(i\) 位，当前 \(i\) 到 \(i-m+1\) 的状态，发现当前连续长为 \(m\) 的区间向后推进时，最左边的舍弃，新来的最右边两种情况讨论 DP ，看最右边填 1 是否合法即可。但我如何在二进制下把最左边的删了，在第一个数位前再加进来一个数？我不会弄，但是如果你这个长为 \(m\) 的区间放在整个长 \(n\) 的数列最右端，向左扫描，那我是不是直接左移一位，然后“与”操作就可以了，实现的时候可以正序，最后答案是一样的。

然而是环，显然我们能把 \(1\) 到 \(m\) 复制一遍放最后，然后判断就行，但是我们要要求 \(n+1\) 到 \(n+m\) 和 \(1\) 到 \(m\) 的数要一样，实际上直接答案是 \(dp[n+m][x]\) 就行， \(x\) 为枚举的 \(1\) 到 \(m\) 的数，代码：

#include<bits/stdc++.h>
#define vd void 
#define int long long 
const int mod=1e9+7;
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
vd inc(int&a,int b){a=a+b>=mod?a+b-mod:a+b;}
int get1(int a){return __builtin_popcount(a);}
int n,m,K,dp[1025][1024],ans=0;
int solve(int x){
	memset(dp,0,sizeof(dp));
	dp[m][x]=1;
	for(int i=m+1;i<=n+m;i++){
		for(int j=0;j<(1<<m);j++){
			if(get1(j)>K)continue;
			inc(dp[i][j],dp[i-1][j>>1]); //最右边为0
			if(get1((j>>1)|(1<<m-1))<=K)inc(dp[i][j],dp[i-1][(j>>1)|(1<<m-1)]); //为1
		}
	}
	return dp[n+m][x];
}
signed main(){ 
	n=gi(),m=gi(),K=gi();
	for(int i=0;i<(1<<m);i++)if(get1(i)<=K)inc(ans,solve(i));
	printf("%lld\n",ans);
	return 0;
}

能够发现， \(dp\) 第一维直接滚掉， \(n\) 很大，而且每个转移都能用矩阵刻画，直接上矩阵快速幂，注意不要像上面一样枚举开始的 \(m\) 个数了，可以直接放到矩阵的对角线上，相乘就可以了，代码：

#include<bits/stdc++.h>
#define vd void 
#define int long long 
const int mod=1e9+7;
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
vd inc(int&a,int b){a=a+b>=mod?a+b-mod:a+b;}
int get1(int a){return __builtin_popcount(a);}
int n,m,K,ans=0;
struct mat{
	int a[35][35];
	mat(){memset(a,0,sizeof(a));}
	vd init(){for(int i=0;i<32;i++)a[i][i]=1;}
	mat operator*(const mat&T)const{
		mat res;
		for(int i=0;i<32;i++)
			for(int j=0;j<32;j++)
				for(int k=0;k<32;k++)res.a[i][j]=(res.a[i][j]+a[i][k]*T.a[k][j]%mod)%mod;
		return res;
	}
	mat operator^(int x)const{
		mat res,g;res.init();
		for(int i=0;i<32;i++)for(int j=0;j<32;j++)g.a[i][j]=a[i][j]%mod;
		while(x){
			if(x&1)res=res*g;
			g=g*g,x>>=1;
		}
		return res;
	}
};
signed main(){ 
	n=gi(),m=gi(),K=gi();
	mat qwq,t;qwq.init();
	for(int i=0;i<(1<<m);i++){
		if(get1(i)>K)continue;
		int j=i>>1;t.a[j][i]=1;j|=(1<<m-1);
		if(get1(j)<=K)t.a[j][i]=1;
	}
	t=t^n,qwq=qwq*t;
	for(int i=0;i<(1<<m);i++)inc(ans,qwq.a[i][i]);
	printf("%lld\n",ans);
	return 0;
}