CFR 327 C. Magic Five ( Math )

Problem - 327C - Codeforces

題意：
給一個大數 A，將其複製 K 次連接成一個新的大數 S。問有多少種方法任意刪除 S 中的數字，使得留下來的數字被 5 整除。允許領導 0，但不允許空字串。兩個方法相同若且唯若兩個方法刪除的數字的位置都是一樣的。

資料規模：
In the first line you're given a string a (1 ≤ |a| ≤ 1e5), containing digits only. In the second line you're given an integer k (1 ≤ k ≤ 1e9). The plate s is formed by concatenating k copies of a together. That is n = |a|·k.

解法：
顯然只要末尾是 0 或 5 就可以被 5 整除。考慮只有 A 的情形，那麼對於所有 A[ i ] == 0 or A[ i ] == 5 的 i ( 由左數，0 based )，只要求 pow( 2, i ) 的總和即可。變成 S 的情形只是對於個別的 i 變成了：i, i + | A |, i + 2 * | A |, ...，其實也就只是

時間 / 空間複雜度：
O( | A | )

MOD = int( 1e9 + 7 )

A = input()
K = int( input() )

ans = 0
q = 1
for i in range( len( A ) ):
  if A[ i ] == '0' or A[ i ] == '5':
    ans = ( ans + q ) % MOD
  q = q * 2 % MOD

print( ans * ( pow( 2, K * len( A ), MOD ) - 1 ) * pow( pow( 2, len( A ), MOD ) - 1, MOD - 2, MOD ) % MOD )