Atcoder arc146 C

C - Even XOR

https://atcoder.jp/contests/arc146/tasks/arc146_c

求多少个 元素值范围在[0,2^N)的集合满足

集合的任意偶数个数的非空子集合,元素xor均不为0

mod 998244353

我的思路

先是在想 线性基, 但实际上 1 2 3 4, 也是合法的, 因为, 虽然3可以由2线性表出,但是它们是3个不是偶数个

---

然后想转移 n -> n+1

显然集合合法,它的子集也是合法

如果n 合法的方案, 拆一部分 高位填,0 另一部分高位填1, 这样的方案一定是合法, 那么 ans[n][len] 乘2^len, 贡献到a[n+1][len]

如果对于n合法,必定不存在 a,a+高位,b,b+高位 同时存在的情况, 因此至多有一个 自身和自身+高位同时存在

那么考虑 合法的选定一个 做这种自身和高位都存在, 剩下的依然拆分, 这样依然是合法的, ans[n][len] * len * 2^{len-1} 贡献到a[n+1][len+1]

---

然后这样似乎能多次做路径计算+组合数可以做

但是问题是 这样算出来 n=3时答案=141, 而正确的是149

也就是漏情况了

可能存在 不合法的n的方案 但是赋予高位0,1 以后变成n+1的方案 就合法了?

那么就是任意在n中 的 xor(A)^xor(B) = 0,

在n+1中 = xor(A)^xor(B+高位) = 高位

也就是n+1 中所有低位产生xor = 0 的必然对应的高位个数是奇数

不会推了

题解

$S$如果合法

$T \subset S,size(T) = 1 \pmod 2, X = xor(T)$

如果$X$加入, 则显然$T + X$ 不合法

因此$S$ 的所有奇个数子集的xor不能被加

任意$U,V \subset S$, 且都是奇数大小

下面证明它们的xor不同

显然 如果相同, 那么两个集合元素合并起来,去掉出现两次的元素, 得到的是个偶数大小且xor = 0 的集合

得证

这里还有个好处是, 本身一个元素也是奇数个,所以不需要额外判重

个数就是经典的 ((1-1)^n + (1+1)^n)/2

---

然后dp一下就没了

dp[0] = 1

dp[1] = 2^n

dp[i] = (dp[i-1] * (2^n - 2^{i-2}) )/i , 每个集合被统计了i次因此除以i

---

emmm 其实我好奇, 我那个想法是不是没法搞

代码

https://atcoder.jp/contests/arc146/submissions/34195315

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;

typedef long long ll;
const int MOD = 998244353;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
ll read(){ll r;scanf("%lld",&r);return r;} // read

mint inv[200010] = {0,1};
mint _pwr2[200010] = {0,1}; // 令 2^-1 = 0
mint *pwr2 = _pwr2+1;

int main(){
  int n = read();
  rep(i,2,n+1+1) inv[i] = (MOD-MOD/i) * inv[MOD%i];
  rep(i,1,n+1) pwr2[i] = pwr2[i-1]*2;
  mint ans = 1; // dp[0] + dp[1] * (1+k1(1+k2(1+k3(...)))), dp[n+2] = 0
  per(i,1,n+1+1) (ans *= (pwr2[n] - pwr2[i-2]) * inv[i]) += 1;
  printf("%d\n",ans.val());
  return 0;
}

总结

C

感觉不知道怎么找切入点, 事后看起来也觉得显然, 也没有不会的知识点

参考

官方题解