杂题

题意

给定(n,m)，初始序列({a_i})全为(0)，可以进行任意次操作，选取一段长度为(m)的区间，依次赋值为(1,2,cdots ,m)
求能得到多少种任意位置非(0)的序列
(n,mle 10^6)

做法

感谢神仙MAOoo的耐心教导

令(f_i(j))为第(i)个位置，填(j)，前(i)个位置不同的方案数
考虑若目前所处的位置(le n-m+1)，那么这个位置可以赋值为任意([1,m])的数：

[egin{aligned} &ile n-m+1 egin{cases} f_i(1)=sumlimits_{k=1}^m f_{i-1}(k)\ f_i(j)=f_{i-1}(m)+f_{i-1}(j-1)(j eq 1) end{cases}\\ &i>n-m+1 egin{cases} f_i(j)=f_{i-1}(m)+f_i(j-1)(jge i-(n-m)) end{cases}\ end{aligned}]

对于(ile n-m+1)
观察到(f_i(j)-f_{i-1}(j-1)=f_{i-1}(m)(j eq 1))
那么就是对于dp数组，滑动窗口，维护一个差值
仅需求出(f_i(1))

对于(i>n-m+1)类似

这道题很难讲得很清楚，所以放份代码

Code

#include<bits/stdc++.h>
typedef int LL;
typedef double dl;
#define opt operator
#define pb push_back
#define pii std::pair<LL,LL>
const LL maxn=1e6+9,mod=1e9+7,inf=0x3f3f3f3f;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
void Chkmax(LL &x,LL y){
	if(y>x) x=y;
}
LL add(LL x,LL y){
	return x+=y,x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
	return x-=y,x<0?x+mod:x;
}
LL mul(LL x,LL y){
	return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
	LL ret(1); while(b){
		if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;
	}return ret;
}
LL n,m;
LL dp[maxn<<1];
int main(){
	LL n(Read()),m(Read());
	LL l(1),r(m);
	dp[r]=1;
	LL delta(0),sum(1);
	++l; ++r;
	for(LL i=1;i<n;++i,++l,++r){
		if(i+1<=n-m+1){
			sum=dec(sum,dp[l-1]);
			dp[r]=add(1ll*(m-2)*delta%mod,sum);
		}
		delta=add(delta,add(delta,dp[l-1]));
		sum=add(sum,dp[r]);
	}
	printf("%d
",add(dp[l-1],delta));
	return 0;
}