これはなに

hackmd.io

こんな感じの「こう考えて解きました」系の記事を書きたくなったので、書きます。 Twitter でツイートするくらいの気持ちで書いているのであんまり丁寧じゃないです（Twitter アカウントが凍結されたので）。考察で当たり方針をさくさく引けた気がするので、そういう感じの記事になります。

問題概要

正整数列 $(A _ i) _ {1\leq i\leq N}\ (1\leq N\leq 1000,0\leq A _ i\leq 1000)$ と正整数 $K\ (1\leq K\leq10^{12})$ が与えられます。

すべての $(X _ i) _ {1\leq i\leq K}\ (1\leq X _ i\leq N)$ にわたる $\displaystyle\sum _ {i=1} ^ KA _ {X _ i}$ の総 xor を求めてください。

第一とっかかり

サンプルを読むと $40$ が 2 つあったので、「$\displaystyle\sum _ {i=1} ^ KA _ {X _ i}$ の値が同じ選び方がいっぱいあるかも、特に偶数通りの選び方で値が同じになるものがいっぱいあるかも」と思いました。

実際いっぱいあって、$A _ i$ を $C _ i$ 回選ぶような選び方は $\dfrac{K!}{\prod _ {i=1} ^ {N}C _ i!}$ 通りあります（これは多項係数というやつです）。

これが奇数になるような条件を考えます。

$K!$ が $2$ で割り切れる回数は、$K+\left\lfloor\dfrac K{2}\right\rfloor+\left\lfloor\dfrac K{2 ^ 2}\right\rfloor+\cdots$ 回で計算できます。これは、$2K-\operatorname{popcount}(K)$ です。この式変形は

atcoder.jp

この問題で行ったことがあるので、比較的すぐできました。

よって、$\dfrac{K!}{\prod _ {i=1} ^ {N}C _ i!}$ が $2$ で割り切れる回数は $\displaystyle\sum _ {i=1} ^ N\operatorname{popcount}(C _ i)-\operatorname{popcount}(K)$ 回です。これが $0$ になるような $C _ i$ の条件が考えたいものでした。

2進法で考えて、 $C _ i$ を合計するときに繰り上がりが生じると $\operatorname{popcount}$ の合計が減ってしまうことから、$C _ i$ は $K$ の $0$ 個以上のビットを重複なく担当している感じだとわかります。

これをぐっと睨むと $K=\displaystyle\sum _ {i=1} ^ x2 ^ {e _ i}\ (e _ i$ は相異なる$)$ に対して、奇数回出現する値は $\displaystyle\sum _ {i=1} ^ x2 ^ {e _ i}A _ {f _ i}$ と書けることがわかります。

よって、この問題は $N ^ x$ 通りの $(f _ i) _ {1\leq i\leq x}\ (1\leq f _ i\leq N)$ に対して $\displaystyle\sum _ {i=1} ^ x2 ^ {e _ i}A _ {f _ i}$ の総 xor を求める問題であることがわかります。

$N ^ K$ 通りが $N ^ x\leq N ^ {\log _ 2 K}$ 通りに減りました。嬉しい。

第二とっかかり

総 xor が欲しいので、ビットごとに考えたいです。

こういう問題は

上の桁から決まる
下の桁から決まる

のどっちかだと解きやすそうです。

総和の xor を計算したいので、繰り上がりを考えると上の桁からは決まりそうにないです。下の桁から考えます。

1 の位はわかりそうです。 $K$ が奇数のときは $A _ i$ の 1 の位の総 xor によって決まりそうですし、偶数のときは $0$ です。

2 の位は、下の結果が流れてくる場合があるかもしれません。ですが、流れてくる値がたかだか $500$ なので、$500\times1000$ だけの時間をかけると、たかだか $1500$ 通りの状態になります（ここを思いつくのにしばし時間がかかりました）。

同様に、下から流れてくる結果がたかだか $1000$ 状態で、$1000\times1000$ だけの時間をかけてたかだか $2000$ 通りの状態を作ることができます。

つまり、$2 ^ k$ の位まで見た結果 $\lbrace s _ 1,s _ 2,\ldots,s _ k\rbrace$ の $k$ 通りの和があったとして、$2 ^ {k+1}$ の位まで見ると $\left\lbrace \dfrac{s _ 1}2+A _ 1,\dfrac{s _ 1}2+A _ 2,\ldots,\dfrac{s _ 1}2+A _ N,\dfrac{s _ 2}2+A _ 1,\dfrac{s _ 2}2+A _ 2,\ldots,\dfrac{s _ 2}2+A _ N,\ldots,\dfrac{s _ k}2+A _ 1,\dfrac{s _ k}2+A _ 2,\ldots,\dfrac{s _ k}2+A _ N\right\rbrace$ のたかだか $kN$ 通りの和があることになります。

このうち偶数回出てきているものを $0$ 個にして奇数回出てきているものを $1$ 個にするとたかだか $2000$ 通りになってうまくいきそうですね。これを繰り返すとうまく計算ができるはずです。 → WA

第三とっかかり

愚直を書いてランダムチェックをかけると $N$ が偶数のときにこわれていそうでした。

1 の位はわかりそうです。$K$ が奇数のときは $A _ i$ の 1 の位の総 xor によって決まりそうですし、偶数のときは $0$ です。

ここで、$A _ i$ の 1 の位の総 xor が 1 なら答えの 1 の位も 1 としていたのが悪かったですね。なぜなら、同じ $1$ の位が $N ^ {x-1}$ 通りあるからですね。

よって、$N$ が偶数のときは最後以外は $0$ にする必要がありました。 → AC

余談

時間計算量は $O(N\max _ i A _ i\log _ 2K)$ になります。が、上の位に移動する操作で $O(N\max _ iA _ i)$ 時間かけるところを、bitset を使って $O(N\max _ iA _ i/w)$ 時間や畳み込みを使って $O(\max _ iA _ i\log\max _ iA _ i)$ 時間にすることができます。

bitset を使って最速になりました。

この節が書きたかったのでこの記事を書いたわけですね。

追記: 無事陥落しました。

実装例

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    using namespace std;

    unsigned long N, K;
    cin >> N >> K;
    vector<unsigned long> A(N);
    for(auto&& a : A)cin >> a;

    vector<unsigned long> possible{0};
    vector<unsigned long> count(2000);
    const auto reconstruct{[&possible, &count]{
        possible.clear();
        for(unsigned long i{}; i < 2000; ++i)if(count[i])possible.emplace_back(i);
        fill(begin(count), end(count), 0UL);
    }};

    unsigned long ans{}, c{};
    while(K){
        ans += (reduce(begin(possible), end(possible)) & N & 1) << c;
        for(const auto i : possible)count[i / 2] ^= 1;
        reconstruct();
        if(K & 1){
            for(const auto i : possible)for(const auto a : A)count[i + a] ^= 1;
            reconstruct();
        }
        K /= 2;
        ++c;
    }

    cout << (ans + (reduce(begin(possible), end(possible), 0UL, bit_xor<>{}) << c)) / 2 << endl;

    return 0;
}