WARush

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

Codeforces #191 Div2 C "Magic Five"

問題

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

n個の数字sが書かれた長いプレートがある。ラハブはいくつかの数字を消し(ひとつも消さなくてもよいが、全てを消す事はできない)"magic number"(5で割り切れる)と呼ばれる数字にしたい。それは、先頭に0があってもよいことに注意せよ。

現在ラハブはmagic numberの作り方が、何パターンあるか数えたい。2つの作り方が違うとは、消した数字のポジションのセットが違う事を意味する。

sをmagic numberにするための作り方が、何パターンあるか出力せよ。sはaがk個繰り返されたものである。

制約

1 <= aの桁数 <= 10^5
1 <= k <= 10^9



チュートリアルを見て

解いた。すっごい数学してる感じがする。

2^0 + 2^(n*1) + 2^(n*2) + 2^(n*3) + ... + 2^(n*k-1)
ただし、kは10^9と巨大

をどうやって一発で出すかが焦点

答えをSと置いて以下のようにすれば一発ででる

2^n * S =       2^(n*1) + 2^(n*2) + 2^(n*3) + ... + 2^(n*k-1) + 2^(n*k)
      S = 2^0 + 2^(n*1) + 2^(n*2) + 2^(n*3) + ... + 2^(n*k-1)

2^n * S - S = (2^n - 1) * S = 2^(n*k) - 2^0

S = (2^(n*k) - 2^0) / (2^n - 1)

ソースコード

const int MOD = 1000000007;
string num;
long long N, K;

long long mod_pow( long long a, long long b ){
    long long r = 1;
    while( b > 0 ){
        if( b & 1 ) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

long long mod_inv( long long a ){
    return mod_pow( a, MOD - 2 );
}

int main() {
    cin >> num;
    cin >> K;
    N = num.length();

    // 2^x
    long long s1 = 0;
    for( int i = 0; i < N; i++ ){
        if( num[i] == '0' || num[i] == '5' ){
            s1 = (s1 + mod_pow( 2, i )) % MOD;
        }
    }

    // 2^(n * k) - 1
    long long s2 = mod_pow( 2, N * K ) - 1;

    // 2^n - 1
    long long s3 = mod_pow( 2, N ) - 1;

    // 答えは2^x * (2^(n * k) - 1) / (2^n - 1)
    long long ans = s1 * s2 % MOD * mod_inv( s3 ) % MOD;

    cout << ans << endl;
}