自动搬运

查看原文

来自洛谷，原作者为

	mysterys 妈呀特容易死

搬运于2025-08-24 23:17:19，当前版本为作者最后更新于2025-05-31 21:10:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不知道为什么出题人题解如此抽象。

思路

1. 对于一段区间的权值，直接前缀积预处理一下就行了。
2. 先考虑如何暴力求，不难发现无法直接枚举，考虑拆贡献。
3. 对于一段合法的区间，其贡献应该是除了这段区间以外，其他区间的已经被配好的方案数。虽然看起来很奇怪，但实现时，我们只需要记录前缀的方案数即可。
4. 发现对于每次转移一定要满足 $a_l=a_r$，于是拿个桶纪录一下即可。记得顺便把前缀方案数给记录一下。

Code

#include<bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define int long long
const int mod=998244353;
const int N=2.5e5+5;
int a[N],n,f[N];
int s[N],g[N];
int ft[45],gt[45],f2t[45];
inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod; b>>=1;
	}
	return res;
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n;s[0]=g[0]=1;
	for(int i=1;i<=n;i++) {cin>>a[i];s[i]=s[i-1]*a[i]%mod;}
	for(int i=1;i<=n;i++) {
		// int res=0,res2=0;
		// for(int j=1;j<=i;j++) {
		// 	if(a[i]==a[j]){
		// 		g[i]=(g[i]+g[j-1])%mod;
		// 		(res+=f[j-1])%=mod; (res2+=g[j-1]*qpow(s[j-1],mod-2)%mod)%=mod;
		// 	}
		// 	f[i]=(res%mod+(res2*s[i]%mod))%mod;
		// }
		(gt[a[i]]+=g[i-1])%=mod; g[i]=gt[a[i]];
		(ft[a[i]]+=f[i-1])%=mod; 
		(f2t[a[i]]+=g[i-1]*qpow(s[i-1],mod-2)%mod)%=mod; 
		f[i]=(ft[a[i]]+f2t[a[i]]*s[i]%mod)%mod;
	} 
	cout<<f[n];
	return 0;
}

时间复杂度：$O(n \log p)$。