/
Update
2 min
补题 | 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} 考虑对集
做法#
容易发现的是:
- 若给定集合 ,那么当 且 时方案数可翻倍。(开头必然有两种)
- 若集合合法,则必须满足:
- 或
考虑对集合的构造,构造到第 位时,前缀若有 个 1, 个 0, 记 ,可得到以下:
这里在 且 正时必须选择 ,因为如果此时消耗 ,那么新状态为 ,永远不可能选择到
代码#
#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;
}
cpp