好可爱的题啊。
没什么性质,考虑直接递推。
\(f_i\) 表示大小为 \(i\) 的合法集合。
添加元素,不能使任何一个大小为奇数的子集异或和为 \(0\)。
那么:
\[f_i = \frac{f_{i-1} (2^n - 2^{i-2})}{i}
\]
除 \(i\) 是因为集合是无序的。
注意到 \(n+1\) 之后 \(f_i\) 恒为 \(0\),所以时间复杂度 \(O(n)\)。
code
// Problem: C - Even XOR
// Contest: AtCoder - AtCoder Regular Contest 146
// URL: https://atcoder.jp/contests/arc146/tasks/arc146_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
if (p < 0) {
return 0;
}
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, f[maxn];
void solve() {
scanf("%lld", &n);
f[0] = 1;
for (int i = 1; i <= n + 1; ++i) {
f[i] = f[i - 1] * (qpow(2, n) - qpow(2, i - 2) + mod) % mod * qpow(i, mod - 2) % mod;
}
ll ans = 0;
for (int i = 0; i <= n + 1; ++i) {
ans = (ans + f[i]) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Even 146atcoder regular contest even atcoder regular contest 146 beginner atcoder contest 146 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 167 atcoder regular contest 164