自动搬运

查看原文

来自洛谷，原作者为

	Semsue NOI2023 Ag

搬运于2025-08-24 22:38:39，当前版本为作者最后更新于2022-06-21 12:20:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

对于一个长度为 $n$ 的序列 $A_1,A_2,\dots, A_n$ 每次你可以选择两个值相同但位置不同的元素 $A_i,A_j$，然后将 $A_i,A_{i+1},\dots, A_j$ 删除.

如果一个序列可以通过上述操作删为空序列，那么就称这个序列是好的。

问有多少长度为 $n$ 且元素在 $[1,m]$ 内的好的序列.

$1\le n\le 3000,1\le m\le 10^9.$

题解

如果有包含关系的那么肯定删那个更大的，于是删除的区间不会有交。

考虑一个序列 $S$，如果 $S+x$ 是 合法的，那么 $S+x+x$ 也必然是合法的。于是可以考虑 dp，设 $f_{i,j,1/0}$ 代表长度为 $i$ 的序列，在后面放 $j$ 种数可以变成合法的，当前是否合法。答案显然为 $\sum f_{n,i,1}$。

考虑如何转移，如果当前合法，那么继续填那 $j$ 种显然会继续合法，并且合法数量不会增多。于是 $f_{i,j,1}\times j\to f_{i+1,j,1}$。如果填剩下的 $m-j$ 种数中的某个，显然不合法了且会多出来一种你填的这个可以消掉变成合法的，于是 $f_{i,j,1}\times (m-j)\to f_{i+1,j+1,0}$。如果当前不合法，显然还是可以转移到合法 $f_{i,j,0}\times j\to f_{i+1,j,1}$。然后考虑第二种转移，和前面唯一的区别是，你如果再选一遍你当前选的，你还是寄。也就是你只能这么转移 $f_{i,j,0}\times (m-j)\to f_{i+1,j,0}$。

总结一下四种转移：

思考一下发现 $i$ 个数的时候最多 $i$ 种合法的，所以时空复杂度均为 $O(n^2)$。

int main(){
	cin>>n>>m;
	f[0][0][1]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			if(f[i][j][1]){
				f[i+1][j][1]=add(f[i+1][j][1],mul(f[i][j][1],j));
				f[i+1][j+1][0]=add(f[i+1][j+1][0],mul(f[i][j][1],dec(m,j)));
			}
			if(f[i][j][0]){
				f[i+1][j][1]=add(f[i+1][j][1],mul(f[i][j][0],j));
				f[i+1][j][0]=add(f[i+1][j][0],mul(f[i][j][0],dec(m,j)));
			}
		}
	}
	for(int i=0;i<=n;i++)ans=add(ans,f[n][i][1]);
	cout<<ans;
	return 0;
}

2023/6/21 修改了错别字。