序列合并

题目描述

$1<n,m\le 10^3,m\le t\le 10^9$

思路

考虑序列的第一位，如果该位确定，那么问题转化为求 $n-1$ 位问题。但这 $n-1$ 位中第一位可能会与整个序列第一位发生合并。我们更希望出现的情况是第一位确定。故设 $p_{i,j}$ 为限制长度为 $i$，首位出现过 $j$ 的概率，即当该序列之前是 $j$ 时发生合并的概率，而在出现了 $j$ 前提下首位保持不变的概率为 $q_{i,j}$。如果第一位保持为 $j$，相当于有后 $i-1$ 位的首位未出现过 $j$，即 $q_{i,j}=1-p_{i-1,j}$。（$j=t$ 时特判，下文不再重复）

当第一位出现了 $j$ 时，可能有两种情况：

1. 两个 $j-1$ 合并，即 $p_{i,j-1}\cdot p_{i-1,j-1}$
2. 直接加入 $j$，概率 $\frac{1}{m}$

在第一位保持为 $j$ 的情况下考虑求解：设以此为前提，期望和为 $g_{i,j}$，则 $ans_i=\sum_{j=1}^{lim}p_{i,j}q_{i,j}g_{i,j}$。设 $f_{i,j}$ 为第一位产生 $j$ 前提下期望和，有：
$$
g_{i,j}=j+\frac{ans_{i-1}-p_{i-1,j}f_{i-1,j}}{q_{i,j}}
$$
考虑求 $f$。讨论 $j$ 是否保持不变，得：
$$
f_{i,j}=q_{i,j}g_{i,j}+(1-q_{i,j})f_{i,j+1}
$$
显然 $lim=\min(n+m-1,t)$，时间复杂度 $O(nm\log(10^9+7))$。但如果不求 $g_{i,j}$，而是求 $q_{i,j}g_{i,j}$，则可以做到 $O(nm)$。

Code

#include<bits/stdc++.h>

using namespace std;

const int mod=1e9+7;
int p[1001][2001],q[1001][2001],g[2001],f[2001],ans;
int m,n,t,lim;

int pow(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1)ret=1LL*ret*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return ret;
}

int main()
{
	freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d%d%d",&n,&m,&t);
	lim=min(n+m-1,t);
	int m_1=pow(m,mod-2),an;
	for(int i=1;i<=n;i++)for(int j=1;j<=lim;j++)p[i][j]=(1LL*p[i][j-1]*p[i-1][j-1]+1LL*(j<=m)*m_1)%mod,q[i][j]=(1-(j<lim)*p[i-1][j]+mod)%mod;
	for(int i=1;i<=lim;i++)g[i]=f[i]=i,ans=(1LL*p[1][i]*q[1][i]%mod*i+ans)%mod;
	for(int i=2;i<=n;i++)
	{
		an=ans;ans=0;
		for(int j=1;j<=lim;j++)
		{
			int _=an-(j<lim?1LL*p[i-1][j]*f[j]%mod:0)+mod;
			g[j]=(1LL*q[i][j]*j+_)%mod;ans=(1LL*p[i][j]*g[j]%mod+ans)%mod;
		}
		for(int j=lim;j;j--)f[j]=(1LL*g[j]%mod+1LL*(1-q[i][j]+mod)*f[j+1]%mod)%mod;
	}
	printf("%d\n",ans);
	return 0;
}

Summary

如果发现无法直接转移，不妨把所需的辅助变量都设出来，多个量一起递推。