D. Sequence

题目

对于给定长度为\(n\)的\(01\)串\(s_1,s_2,\dots,s_n\),定义:

\([]\)为艾弗森括号,belike:

if p==true:[p]=1
else:[p]=0

现在给你长度\(n\)和\(\{p_1',p_2',\dots,p_n'\}\)(下称多重集合\(p'\)),表示被打乱的\(\{p_1,p_2,\dots,p_n\}\)(下称\(p\)序列).

求有多少\(01\)串符合条件(即符合\(p\)序列).

题目保证至少有一个串符合条件.

输入描述

第一行,一个整数\(n\);

第二行,\(n\)个整数\(p_1',p_2',\dots,p_n'\).

输出描述

一个整数,答案对\(998244353\)取模.

思路

令\(cnt_{i, 0}\)表示\(s_1,s_2,\dots,s_i\)中\(0\)的数量,\(cnt_{i,1}\)表示\(1\)的数量;

1.等价类

思考对于一个\(01\)串,有哪些串与其拥有相同的\(p\)序列.

启发: 把\(01\)串整体取反得到的新串与原串拥有相同的\(p\)序列.

命题1（充分性）: 若\(s_1,s_2,\dots,s_k\)（\(0\le k）中\(0\)和\(1\)的数量相同,则把\(s_{k+1},\dots,s_n\)取反后得到的新串\(\{s_1,\dots,s_k,s_{k+1}',\dots,s_n'\}\)与原串拥有相同的\(p\)序列.

证明:

注:下面用\(p'\)表示新串的\(p\)序列,请与题面中的多重集合\(p'\)区分开.

首先\(p_1,p_2,\dots,p_k\)没有变化是显然的;

由于\(cnt_{k,0}=cnt_{k,1}=p_k\),不妨设原串中,\(s_{k+i}=0\),则

\[\begin{align*}p_{k+i}&=cnt_{k+i,1}=cnt_{k,1}+cnt_{k+i,1}-cnt_{k,1}\\&=p_k+(cnt_{k+i,1}-cnt_{k,1})\end{align*} \]

\(cnt_{k+i,1}-cnt_{k,1}\)是子串\(\{s_{k+1},\dots,s_{k+i}\}\)中\(1\)的数量;

而新串中,\(s_{k+i}'=1\),则\(p_{k+i}'=p_k'+(cnt_{k+i,0}'-cnt_{k,0}')\),

\(cnt_{k+i,0}'-cnt_{k,0}'\)是子串\(\{s_{k+1}',\dots,s_{k+i}'\}\)中\(0\)的数量,

由新串的构造方式知\(cnt_{k+i,1}-cnt_{k,1}=cnt_{k+i,0}'-cnt_{k,0}'\),

因此\(p_{k+i}=p_{k+i}'\),\(1\le i\le n-k\),证毕.

命题2（必要性）: 若\(01\)串\(s\)、\(s'\)（\(s\ne s'\)）拥有相同\(p\)序列,则\(s'\)必可由\(s\)通过有限次平衡点之后的后缀取反得到（即推论1所描述的取反方式）.

证明: 归纳法.

假设\(i\)是二者第一个不同的位置,则对于\(j=1,2,\dots,i-1\)有: \(s_j=s_j'\),\(cnt_{j,0}=cnt_{j,0}'\),\(cnt_{j,1}=cnt_{j,1}'\).

不妨设\(s_i=0\),则\(p_i=cnt_{i,1}=cnt_{i-1,1}\); 相应的,\(s_i'=1\),且\(p_i'=cnt_{i,0}'=cnt_{i-1,0}'\).

又由于\(p_i=p_i'\),因此\(cnt_{i,1}=cnt_{i,0}'\), 所以\(cnt_{i-1,1}=cnt_{i-1,0}'=cnt_{i-1,0}\),即\(i-1\)是平衡点.

将\(s\)串从\(i\)开始后缀取反后,再找下一个与\(s'\)不同的位置,可得到类似结论. 因串的长度有限,故经过有限次平衡点之后的后缀取反即可把\(s\)变为\(s'\).

这样就证明了两个\(01\)串"有相同\(p\)序列"等价于"可通过若干次平衡点之后的后缀取反相互转化".

对于一个\(01\)串\(s\),从前到后找到每一个\(cnt_{i,0}=cnt_{i,1}\)的位置,若\(s_{i+1}=1\)则让\(\{s_{i+1},\dots,s_n\}\)取反.这样操作后得到的新串满足:

\(cnt_{i,0}'\ge cnt_{i,1}'\),\(i=1,2,\dots,n\),即任意前缀\(0\)的数量不少于\(1\)的数量.

这个串可称为\(s\)的规范串,也就是对应\(p\)序列的规范串.

规范串唯一性证明:

反证法.假设串\(s\ne t\)拥有相同\(p\)序列且均满足任意前缀\(0\)的数量不少于\(1\)的数,假设\(i\)是二者不同的第一个位置,由已有结论可知\(i-1\)是平衡点,由于\(s_i\)和\(t_i\)必有一个为\(1\),因此\(s\)和\(t\)中必有一个满足前缀\(i\)中\(0\)的数量少于\(1\)的数量,矛盾.

因此,"给定\(p\)序列对应多少\(01\)串"等价于"给定规范串对应多少后缀取反等价串".

每一个可以开始取反的位置,可以把一个串分裂为两个,因此:

\(ans=2^{{}count}\),其中\(count\)为满足\(cnt_{i-1,0}=cnt_{i-1,1}\)的\(i\)的数量.

2.还原多重集合p'

考虑根据\(p'\)构造规范串,题目保证有解,因此规范串必存在.

为方便表示,让\(a=cnt_{i-1,0}\),\(b=cnt_{i-1,1}\),\(a\ge b\)

若令\(s_i=0\),则\(p_i=b\),\(a'=+1\),\(b'=b\phantom{+1}\);

若令\(s_i=1\),则\(p_i=a\),\(a'=a\phantom{+1}\),\(b'=b+1\);

令\(cnt_i[x]\)表示到位置\(i\)时多重集合\(p'\)中还未被使用的\(x\)的数量

则有\(\sum_{x=0}^{N}cnt_i[x]=\sum_{x=b}^{N}cnt_i[x]=n-i+1\).

对于第\(i\)个位置:

若\(cnt_i[a]>0,cnt_i[b]=0\),则只能令\(s_i=1\);

若\(cnt_i[a]=0,cnt_i[b]>0\),则只能令\(s_i=0\);

若\(cnt_i[a]>0,cnt_i[b]>0\),则只能令\(s_i=0\);

前两条很容易理解,下面解释第三条:

若\(a=b\),由规范串的构造原理可知,应当令\(s_i=0\);

若\(a>b\),假设令\(s_i=1\),则\(a'=a\ge b'=b+1>b\),

又\(\{cnt_{i,0}\}\)和\(\{cnt_{i,1}\}\)都是单调递增的,

这意味着二者都再也不会回到\(b\),

#include 
using namespace std;const int N = 1e5 + 10, MOD = 998244353;int n, cnt[N];signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n;for (int i = 1; i <= n; i++) {int x; cin >> x;cnt[x]++;}int ans = 1, a = 0, b = 0;for (int i = 1; i <= n; i++) {if (a == b) ans = ans * 2 % MOD;if (cnt[b]) a++, cnt[b]--;else b++, cnt[a]--;}cout << ans << endl;return 0;
}