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; }