WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #191 Div2 E "Axis Walking"

問題

http://codeforces.com/contest/327/problem/E

あとで

制約

あとで


チュートリアルを見て

よくわからん。

O(2^N * N)はだめ!O(3^(N/2) * N^2)がいいって言ってるけど、4億と3億であんまり違いが無いような・・・。それに、後者のほうは1つ1つの処理が重いから結局前者のほうが速かったというね。

うーん・・・。

結局ビットDPで通す。

事後

合計値(ソースコードのs)のとり方は他の人のを参考にしたんだけどカッコイイよね。
蟻本にもあったけど(i & -i)でiの一番下位の1のビットを取り出せるのを利用している。


ソースコード

const int MOD = 1000000007;

int n;
int k;
int k1, k2;
long long a[1<<24];
long long s[1<<24];
int dp[1<<24];

int main() {
    // 入力
    cin >> n;
    for( int i = 0; i < n; i++ ){
        cin >> a[1<<i];
    }
    k1 = k2 = -1;
    cin >> k;
    if( k == 1 ){
        cin >> k1;
    }else if( k == 2 ){
        cin >> k1 >> k2;
    }


    // dp初期化
    memset( dp, 0, sizeof(dp) );
    dp[0] = 1;
    s[0] = 0;

    // dp更新
    for( int b = 0; b < 1 << n; b++ ){
        s[b] = s[b - (b & -b)] + a[b & -b];
        if( s[b] == k1 || s[b] == k2 ) dp[b] = 0;
        if( dp[b] == 0 ) continue;

        for( int i = 0; i < n; i++ ){
            int m = 1 << i;
            if( b & m ) continue;
            int nb = b | m;
            dp[nb] = dp[nb] + dp[b];
            if( dp[nb] > MOD ) dp[nb] -= MOD;
        }
    }

    cout << dp[(1<<n)-1] << endl;
}