WARush

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

Codeforces #189 Div2 C "Malek Dance Club"

問題

http://codeforces.com/contest/320/problem/C

伝統として、毎年、ナタリアファンクラブは共に一夜を一緒に楽しむため、マレクダンスクラブを招待していた。マレクダンスクラブは2^n人のメンバーがおり、偶然にもナタリアファンクラブもまた2^n人のメンバーがいる。MDCの各メンバーは0~2^n-1番の一意である会員番号を持っており、NFCのメンバーも同じように会員番号をもっていた。

この夜のイベントの一つに、MDCの各メンバーがNFCの各メンバーとダンスするというものがあった。ダンスのペアは、MDCから会員番号aと、NFCから会員番号bという一つの数値のペア、(a, b)で表される。

割り当てられたペアの複雑さとは、a < cかつb > dとなる2組(a, b)と(c, d)が何組あるかで表される。

あなたは2進数表記で長さがnとなるxという数字が与えられる。MDCのメンバー i は、NFCのメンバー i^x とペアを組んでいた。この時のペアの組み方の複雑さを計算せよ。

制約

1 <= n <= 100


考えた事

全然分からん・・・全然分からんのだが、1 << (n - 1)を一番右のビットの重みとして計算すればいいってことは分かった。
証明とかどうやんのこれ・・・


ソースコード

int main() {
    string x;
    cin >> x;
    int n = x.length();

    const int MOD = 1000000007;

    long long a = 1;
    for( int i = 1; i < n; i++ ){
        a = a * 2 % MOD;
    }
    long long r = 0;
    for( int i = n - 1; i >= 0; i-- ){
        if( x[i] == '1' ){
            r = (r + a) % MOD;
        }
        a = a * 2 % MOD;
    }

    cout << r << endl;
}