結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-24 19:01:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,251 bytes
コンパイル時間 1,165 ms
コンパイル使用メモリ 87,152 KB
実行使用メモリ 77,576 KB
最終ジャッジ日時 2023-09-25 16:43:55
合計ジャッジ時間 1,395 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def dist(qs, Q):
    dp = [[0] * (qs[-1]*Q+1) for _ in range(Q + 1)]
    dp[0][0] = 1
    for q in qs:
        for n in range(1, Q + 1):
            for s in range(q, q*n+1): dp[n][s] += dp[n-1][s-q]
    return dp[Q]

def mult(ps1, ps2, f, mod):
    n = len(f)
    ps = [0] * (2*n-1)
    for i, p1 in enumerate(ps1):
        for j, p2 in enumerate(ps2): ps[i + j] += p1 * p2
    for i in range(2*n-2, n-1, -1):
        p = ps[i] % mod
        for j, fk in enumerate(f, i - n): ps[j] += p * fk
    return [p % mod for p in ps[:n]]

N, P, C = map(int, input().split())
mod = 10**9+7
dpp = dist([2, 3, 5, 7, 11, 13], P)
dpc = dist([4, 6, 8, 9, 10, 12], C)
cs = [0] * (len(dpp) + len(dpc) - 1)
for i, pi in enumerate(dpp):
    for ij, cj in enumerate(dpc, i): cs[ij] += pi * cj
cs = [c % mod for c in cs]
cs.reverse()
k = len(cs)
bs = [1]
for i in range(1, k): bs.append(sum(a*c for a, c, in zip(bs, cs[-i:])) % mod)
ts = [0] * k
cum = sum(cs)
for i in range(k):
    ds = [0] * i + bs[:k-i]
    for j in range(k): ts[j] += ds[j]*cum
    cum -= cs[k-i-1]
psR = [1] + [0] * (k-1)
ps = [0, 1] + [0] * (k-2)
p = N-1
while p:
    if p & 1: psR = mult(ps, psR, cs, mod)
    ps = mult(ps, ps, cs, mod)
    p >>= 1
print(sum(p * t for p, t in zip(psR, ts)) % mod)
0