結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー 👑 rin204rin204
提出日時 2022-10-02 13:58:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 937 ms / 3,000 ms
コード長 1,462 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 76,200 KB
最終ジャッジ日時 2024-12-25 02:02:48
合計ジャッジ時間 2,535 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 380 ms
76,200 KB
testcase_01 AC 937 ms
76,156 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10 ** 9 + 7

def multiply(A, B):
    n = len(A)
    m = len(B)
    C = [0] * (n + m - 1)
    for i, a in enumerate(A):
        for j, b in enumerate(B):
            C[i + j] += a * b
            C[i + j] %= MOD
    return C

# [x ^ n] P(x) / Q(x)
def BostanMori(P, Q, n):    
    while n:
        R = [(x * (-1) ** (i % 2)) % MOD for i, x in enumerate(Q)]
        Q = multiply(Q, R)[::2]
        P = multiply(P, R)[n % 2::2]
        n >>= 1
    return P[0] * pow(Q[0], MOD - 2, MOD) % MOD


n, P, C = map(int, input().split())
prime = [2, 3, 5, 7, 11, 13]
comp = [4, 6, 8, 9, 10, 12]

def make_dp(P, C):
    pp = [0] * (13 * P + 1)

    def dfs_pp(i, j, tot):
        if i == 6:
            if j == P:
                pp[tot] += 1
            return

        for k in range(j, P + 1):
            dfs_pp(i + 1, k, tot)
            tot += prime[i]
    
    dfs_pp(0, 0, 0)
    
    cc = [0] * (12 * C + 1)

    def dfs_cc(i, j, tot):
        if i == 6:
            if j == C:
                cc[tot] += 1
            return

        for k in range(j, C + 1):
            dfs_cc(i + 1, k, tot)
            tot += comp[i]
    
    dfs_cc(0, 0, 0)

    return multiply(pp, cc)

dp = make_dp(P, C)
Q = [MOD - d for d in dp]
Q[0] = 1
ma = len(dp) - 1
for i in range(ma - 1, -1, -1):
    dp[i] += dp[i + 1]
    dp[i] %= MOD

ans = 0
for i in range(max(0, n - ma), n):
    ret = BostanMori([1], Q, i)
    ans += ret * dp[n - i]
    ans %= MOD
print(ans)
0