ARC146 C - Even XOR (600, 橙)

• 問題文
• 正解コード(C++)

お気持ち

• 本番は、「奇数個OKの条件がなければ／0が必ずSに含まれる場合なら」簡単なのになぁと思いながら複雑に考えてしまい、頭が爆発しました。
• 最初に思いつきやすいのは、以下の性質かなと思います。そして、この辺の考えがグルグル回ってしまい、収集がつかなくなるのも日常茶飯事。
  • (1) 集合Sが独立なら部分集合のXORは相異なる
  • (2) 集合Sが独立という条件なら数え上げが簡単
  • (3) 集合Sに必ず0を入れるパターンはS/{0}が独立ならOK
• あながち悪い方針ではないですが、(2)(3)は特殊ケースの性質になっていて、(1)や(1)の証明に使われる性質を上手く活かせていない気がします。もう少し基本的な性質を見ていきたいですね。

考察

基本的な操作に対して、いい性質を見つけていく感じで解けました。 2枚目のメモにWAと書いてありますが、解法は正しいです。 最初、サンプル1の答えが11になったので首をかしげていましたが、 の逆元を計算していなかっただけでした。

重要な性質

漸化式の考察

ソースコード

#include <iostream>
#include <atcoder/modint>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
using namespace atcoder;
using mint = modint998244353;

int n;
mint dp[200002][2];
mint pw2[200002];
mint inv[200002], fact[200002], finv[200002]; //(n+1)!の逆数まで使うので注意

void init(int n) {
    int i;
    pw2[0] = 1; rep(i, n) pw2[i + 1] = pw2[i] * 2;
    inv[1] = fact[1] = fact[0] = finv[1] = finv[0] = 1;
    int mod = 998244353;
    for (i = 2; i <= n; i++) {
        fact[i] = i * fact[i - 1];
        inv[i] = -inv[mod % i] * (mod / i);
        finv[i] = inv[i] * finv[i - 1];
    }
}

int main() {
    int i, j;
    
    cin >> n;
    init(n + 1);

    dp[0][0] = 1; dp[0][1] = 0;
    dp[1][0] = pw2[n] - 1; dp[1][1] = 1;
    for (i = 1; i <= n; i++) {
        dp[i + 1][0] = dp[i][0] * (pw2[n] - pw2[i]);
        dp[i + 1][1] = dp[i][0] * pw2[i - 1] + dp[i][1] * (pw2[n] - pw2[i - 1]);
    }

    mint ans = 0;
    rep(i, n + 2) {
        ans += (dp[i][0] + dp[i][1]) * finv[i];
    }

    cout << ans.val() << endl;
    return 0;
}