3 views
补题 | ICPC EC 线上一 D
做法 容易发现的是： 若给定集合 \{p_1,p_2,\cdots,p_n\} ，那么当 p_i=p_{i+1} 且 p_i+p_{i+1}=i 时方案数可翻倍。（开头必然有两种） 若集合合法，则必须满足： p_i < i p_i + p_{i+1} = i 或 p_i = p_{i+1} 考虑对集
做法
容易发现的是：
- 若给定集合 \{p_1,p_2,\cdots,p_n\} ，那么当 p_i=p_{i+1} 且 p_i+p_{i+1}=i 时方案数可翻倍。（开头必然有两种）
- 若集合合法，则必须满足：
- p_i < i
- p_i + p_{i+1} = i 或 p_i = p_{i+1}
考虑对集合的构造，构造到第 i 位时，前缀若有 A 个 1, B 个 0， 记 x=\min (A,B),y=\max(A,B) ，可得到以下：
\begin{array}{c|c|c} \text{条件}&\text{消耗的值}&\text{新状态}\\ \hline x<y,\ \operatorname{cnt}[x]>0 & x &(x,y+1)\\ x<y,\ \operatorname{cnt}[x]=0 & y &(x+1,y)\\ x=y & x &(x,y+1) \end{array}
这里在 x<y 且 cnt[x] 正时必须选择 x ，因为如果此时消耗 y ，那么新状态为 (x+1,y) ，永远不可能选择到 x
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
struct mint {
...
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> cnt(n + 1);
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
cnt[t]++;
}
mint ans = 1;
int x = 0, y = 0;
for (int i = 1; i <= n; i++) {
if (x == y) {
ans *= 2;
cnt[x]--;
y++;
} else if (cnt[x] > 0) {
cnt[x]--;
y++;
} else {
cnt[y]--;
x++;
}
}
cout << ans.x << "\n";
return 0;
}