solution-P12674

mysterys · 2025-05-31 21:10:23 · 题解

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

思路

对于一段区间的权值，直接前缀积预处理一下就行了。
先考虑如何暴力求，不难发现无法直接枚举，考虑拆贡献。
对于一段合法的区间，其贡献应该是除了这段区间以外，其他区间的已经被配好的方案数。虽然看起来很奇怪，但实现时，我们只需要记录前缀的方案数即可。
发现对于每次转移一定要满足 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)。

solution-P12674

思路

Code