主播主播，你的组合数学确实很强，可是还是太吃码力了，有没有代码简单，又跑得飞快的做法呢？

有的兄弟，有的，这样的做法还有114种

来发一篇dp题解

注意到这一题可以状态转移

设 $f_i$ 为前 $i$ 个数满足要求的方式的个数

边界 :

• 注意到当 $i \leq k$ 时，只能填一个 $1$ 或者全是 $0$ ，就有 for (int i=0;i<=k;i++) f[i]=i+1;

转移方程如下：

• 如果第 $i$ 位填 $0$ ，那么 f[i]+=f[i-1]

• 如果第 $i$ 位填 $1$ ，那么 $[i-k,i]$ 之间不能有 $1$ ，就有 f[i]+=f[i-k-1] ，相当于将中间补上了零

• 那么总转移方程 f[i]=f[i-1]+f[i-k-1]

目标：

• $f_N$

于是有一个超级无敌螺旋升天劈里啪啦短的代码：

#include<iostream>
#include<cstdio>

using namespace std;

int n,k,f[10000007];

int main(){
	scanf("%d%d",&n,&k);
	for (int i=0;i<=k;i++) f[i]=i+1;
	for (int i=k+1;i<=n;i++) f[i]=(f[i-1]+f[i-k-1])%998244353;
	printf("%d",f[n]);
	return 0;
} 

短小精悍，总用时 360ms ，跑得飞快

首先我们可以枚举 $1$ 的个数，然后因为任意两个 $1$ 之间要至少要放 $k$ 个 $0$

所以说我们把这些必须放的 $0$ 放进去后，然后剩下的 $0$ 就可以随便放了

如果说当前放了 $i$ 个 $1$ ，也就是说把剩下的 $0$ 放在 $i+1$ 个盒子，并且可以空的方案数

最后统计答案即可

#include<iostream>
#include<cstdio>
#define int long long
#define mod 998244353
using namespace std;
bool Test_MLE_start;
const int N=1e7+10;
int T=1,n,k,ans=1;
int fac[N],inv[N];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
int ksm(int a,int b,int p){
	int ans=1;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%p;
		a=a*a%p;
	}
	return ans;
}
int C(int n,int m){
	if(n<m) return 0;
	if(!inv[m]) inv[m]=ksm(fac[m],mod-2,mod);
	if(!inv[n-m]) inv[n-m]=ksm(fac[n-m],mod-2,mod);
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int calc(int n,int m){
	return C(n+m-1,m-1);
}

bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		n=reads(),k=reads();
		fac[0]=1;
		for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
		for(int i=1;;i++){
			if(i+(i-1)*k>n) break;
			int now=n-i-(i-1)*k;//now same ball put in i+1 not-same box,so ans=C(i+now,i)
			ans=(ans+calc(now,i+1))%mod;
//			cout<<i<<":"<<C(now+i,i)<<"\n";
//			cout<<"box:"<<i+1<<" ball:"<<now<<" "<<now+i<<" "<<i<<"\n";
		}
		printf("%lld\n",ans);
	}
	return 0;
}