题解 P1370 【Charlie的云笔记序列】

· · 题解

这题好难啊。。如果没有一个题解真的不好做。

首先要统计所有F(l,r)

设dp[i]为F[i,i],F[i,i+1],F[i,i+2].....F[i,n]的和

显然如果没有重复的数字的话,dp[i]=dp[i+1]*2+2;

很好理解，就是在F[i+1,i+1],F[i+1,i+2].....F[i+1,n]的前面填上或不填ai。再加上F[i,i]=2

然后就到了去重部分

若ai==aj(i<j)

则dp[i]-=dp[j+1]+1;

原因是 后面所有的F[j+1,j+1].....都会有一次重复(接ai,接aj)

而前面的F[i,j]也会有一次重复(只有ai或只有aj)

所以dp方程就出来了

dp[i]=dp[i+1]*2+2;

dp[i]-=dp[j+1]+1;（ai==aj）

...

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
#ifdef ONLINE_JUDGE
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin)),TT==mo)?0:*TT++)
#endif
inline int read(){
    int x=0,c=0,f=1;
    for(;c<'0'||c>'9';c=getchar())f=c!='-';
    for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
    return f?x:-x;
}
int head[100010];
int a[100010],b[100010];
ll dp[100010];
ll ans;
int n;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=a[i];
    } 
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    dp[n]=2;
    head[a[n]]=n;
    for(int i=n-1;i>0;i--){
        dp[i]=(dp[i+1]*2+2)%mod;
        if(head[a[i]]){
            dp[i]=(dp[i]-dp[head[a[i]]+1]+mod-1)%mod;
            head[a[i]]=i;
        }
        head[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        ans=(ans+dp[i])%mod;
    }
    cout<<ans;
    return 0;
}

...