Submission #32588657

---

Source Code Expand

from itertools import accumulate

def kaisetsu3(N, B, K, c):
    MOD = 1000000007

    *ten, = accumulate(range(10, 72), lambda acc, _: (acc ** 2) % B)
    
    def mul(x, exp, y):
        res = [0] * B
        for p in range(B):
            for q in range(B):
                nex = (ten[exp] * p + q) % B
                res[nex] += x[p] * y[q]
                res[nex] %= MOD
        
        return res
        
    # dp[1][i] を求める
    doubled = [0] * B
    for k in c:
        doubled[k%B] += 1
    
    if N & 1:
        ans = doubled
    else:
        ans = [0] * B
        ans[0] = 1
    N >>= 1
    
    exp = 0
    while N:
        # 2^epx桁目から2^(exp+1)桁目を計算
        doubled = mul(doubled, exp, doubled)
        exp += 1
        if N & 1:
            ans = mul(ans, exp, doubled)

        N >>= 1
    return ans[0]
  

N, B, K, *c = map(int, open(0).read().split())
print(kaisetsu3(N, B, K, c))

Submission Info

Judge Result