n-sequences

对于?个序列\(S\)，令\(L(S)\)表示\(S\)中最长的值相同的子串的?度。

令\(f(n)\)表示对于所有\(n^n\)个长度为\(n\)的每个数值都在\(1\)到\(n\)之间序列的\(L\)值总和。

求\(f(7.5e6)\)。

题解

?先转化为求\(L(S)\geq 1, L(S)\geq 2, …\)的方案然后相加。

接着补集转化为\(L(S)\leq k\)的方案，也就是每段都不超过\(k\)的方案。

设\(g(i)\)表示满足条件的长度为\(i\)的序列的种数，有\(g(0)=1\)。

1. 当\(1\leq i\leq k\)时，\(g(i)=n\times g(i-1)\)。

2. 当\(i=k+1\)时，恰好有\(n\)种方案不合法，\(g(i)=n\times g(i-1)-n\times g(0)\)。

3. 当\(k+2\leq i\leq n\)时，容斥掉\(i-k\sim i\)都是同色的的方案。那么由于\(g(i-1)\)的限制，\(i-k-1\)和\(i-k\)的颜色必须不同。所以\(g(i)=n\times g(i-1)-(n-1)\times g(i-k-1)\)。

直接计算的话时间复杂度\(O(n^2)\)不可取。

CO int N=100;
int64 g[N];

int main(){
	int n=11;
	int64 pwr=pow(n,n),ans=0;
	for(int k=0;k<n;++k){
		g[0]=1;
		for(int i=1;i<=k;++i) g[i]=n*g[i-1];
		g[k+1]=n*g[k]-n*g[0];
		for(int i=k+2;i<=n;++i) g[i]=n*g[i-1]-(n-1)*g[i-k-1];
		ans+=pwr-g[n];
	}
	printf("%lld\n",ans);
	return 0;
}

假设没有第2种转移，考虑这个递推式的组合意义。相当于走楼梯，往上走\(1\)步的代价是乘\(n\)，走\(k+1\)步的代价是乘\(-(n-1)\)。

那么我们枚举一共做了多少次走\(k+1\)步

第二种转移无非是枚举第一次的决策拆开来计算

时间复杂度调和级数\(O(n\ln n)\)。

CO int N=1e7;
int fac[N],ifac[N];
int pn[N],p1n[N];

IN int C(int n,int m){
	if(n<m) return 0;
	return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int main(){
	int n=7.5e6;
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
	ifac[n]=fpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
	pn[0]=p1n[0]=1;
	for(int i=1;i<=n;++i){
		pn[i]=mul(pn[i-1],n);
		p1n[i]=mul(p1n[i-1],1+mod-n);
	}
	int ans=0;
	for(int k=0;k<n;++k){
		if(k==0){
			ans=add(ans,pn[n]);
			continue;
		}
		int sum=0;
		for(int i=0;i*(k+1)<=n;++i){
			if(i==0){
				sum=add(sum,pn[n]);
				continue;
			}
			sum=add(sum,mul(pn[n-i*(k+1)],mul(p1n[i],C(n-i*(k+1)-1+i,i))));
			sum=add(sum,mod-mul(pn[n-i*(k+1)+1],mul(p1n[i-1],C(n-i*(k+1)+i-1,i-1))));
		}
		ans=add(ans,add(pn[n],mod-sum));
	}
	printf("%d\n",ans);
	return 0;
}

PE427 n-sequences

原文：https://www.cnblogs.com/autoint/p/13356885.html