Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Code Thanks Festival 2017-F Limited Xor Subset】DPの計算量を減らすテクニック

F - Limited Xor Subset

問題

数列Aからいくつか選んでxorをKにする方法は何通りあるか?

制約: N=105, Sum(A)=105

方針

Aの頭から1つずつとるかとらないかの選択をするナップザック的なDPをすれば、明らかに答えにはたどり着きますが、Sum(A)が105であることを利用して、xorの上限がせいぜい105であることを利用しても、計算量は1010なので破綻します。(Aの要素がすべてビット衝突しない場合、xor=sumとなり、これがxorの最大です。この性質を利用した問題はたまに見ます)

2つの方針で計算量を減らすことが出来ます。

方針1

Aをソートして、DPします。この時、小さい方からxorしていけば、値がいきなり極端に大きくなることはなく、たかだかそこまでの要素のorで制限することが出来ます。

無駄なくorが上がっていく1,2,4,8,...という最悪ケースを想像すれば、計算量はO(S)となんとなくわかります。

方針2

和がせいぜい105で、Nが105ということは、Nが大きい時を考えると、ほとんどの要素が1や2であることが想像出来ます。従って、重複がたくさんあります。この性質を使って計算量を削減出来ます。

要素とその個数を計算しておきます。

すると、その要素xを使う時に、xorに対する貢献はxか0です。個数をMとすると、M-1の使う使わないはどう選んでもよいけど、最後の1つを恣意的に選べば、xか0を切り替えることが出来ます。つまり、xになる場合は2M-1通りで、0になる場合も2M-1通りです。この倍率を使ってDPをします。

要素の数は最悪でsqrt(S)程度です。従って、O(S sqrt(S))で計算が出来ます。

実装

2つMLEしてしまってますが、方針2の実装です。

fn solve() {
    input!{
        N:usize,K:u64,
        a:[u64;N]
    }

    let mo = 1_000_000_007;

    let mut cnt = vec![0;100001];
    for ai in a {
        cnt[ai as usize]+=1;
    }
    let mut b = vec![];
    let mut c = vec![];
    for i in 0..cnt.len() {
        if cnt[i]>0 {
            b.push(i);
            c.push(cnt[i]);
        }
    }
    let B = b.len();
    let mut dp = vec![vec![0;100001];B+1];
    dp[0][0]=1;
    for i in 0..B {
        for j in 0..100001 {
            let p = modpow(2, c[i]-1, mo);
            if dp[i][j] != 0 {
                dp[i+1][j] += p * dp[i][j];
                dp[i+1][j] %= mo;
                dp[i+1][j^b[i]] += p * dp[i][j];
                dp[i+1][j^b[i]] %= mo;
            }
        }
    }
    println!("{}",dp[B][K as usize]);
}

考察

難しい問題になってくると、問題の性質を利用して計算量を削減する場合も多く、今回のように和に関する制約がある場合は多いですね。あとはビットごとに分けるとか、ルートをとって計算量を減らすとかいうテクニックもあります。