題目描述

有一個長度為 \(n\)，元素大小為 \(0\to n-1\) 的排列 \(q\)。給出它的最小前綴和后綴數組，求其所有可能的 \(q\) 的 \(\sum_{1\le l\le r\le n}\operatorname{mex}_{l\le i\le r}q_i\) 之和。答案對 \(998244353\) 取模。

題解

首先發現了只要最小前綴和后綴數組是確定的，我們的任意 \(q\) 的權值都是一樣的。為什么？我們不用出題人的 trick 解釋，我們換一種：

• 先找到確定的數，我們從小到大找被確定的數，發現只有都包含這些數，這個區間才有貢獻。
• 如果一個數是確定的，那么一定在當前最小包含所有確定的數的區間外。
• 同理，不確定的數一定在當前包含的區間以內。證明：如果在區間外，那么一定有一個在這個不確定的數之外的更小的數，但是這個更小的數是被包含在區間內的，與假設不同，證畢。

所以我們只需要確定不確定的數有多少種填放可能。

根據上面的性質，我們在確定區間時同時計算方案數。因為這個數一定在區間內，而在區間內有沒有其他限制。所以我們有以下方案：

• 我們每有一個不確定的數 \(i\) 時，若當前最小的包含所有數的區間為 \([l,r]\)，則方案數會乘上 \(r-l-i+1\)。
• 我們每有一個確定的數時，我們更新區間，并且所有包含這個區間的方案貢獻 \(+1\)，用容斥計算這個貢獻就可以了。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=998244353;
int n,m,q,T,a[N],b[N],c[N],d[N],cnt;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        int ans=0, pw=1;
        for(int i=0;i<n;i++) c[i]=0;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        c[a[1]]=1;c[b[n]]=n;int l=c[0], r=c[0];
        for(int i=2;i<=n;i++){if(a[i-1]!=a[i]) c[a[i]]=i;}
        for(int i=n-1;i>=1;i--){if(b[i+1]!=b[i]) c[b[i]]=i;}
        for(int i=0;i<n;i++){
            if(c[i]){l=min(c[i],l);r=max(c[i],r);}
			else pw=pw*(r-l+1-i)%mod;
            ans=(ans+l*(n-r+1)%mod)%mod;
        }cout<<ans*pw%mod<<'\n';
    }
    return 0;
}