結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-22 20:28:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,697 bytes
コンパイル時間 144 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 93,552 KB
最終ジャッジ日時 2024-07-18 12:49:17
合計ジャッジ時間 8,436 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

def solve(N, P, C):
    mod = 10 ** 9 + 7
    ps = [2-2, 3-2, 5-2, 7-2, 11-2, 13-2]
    cs = [4-4, 6-4, 8-4, 9-4, 10-4, 12-4] 
    distp = get_dist(ps, P)
    distc = get_dist(cs, C)
    dist = merge_dists(distp, distc)
    dist = [0] * (2 * P + 4 * C - 1) + dist + [0]
    mat = get_mat(dist)
    matN = matrix_pow(mat, N - 1, mod)
    return finalize(matN, dist, mod)


def get_dist(qs, Q):
    '''
    qs を合計Q個使った和が、何通りの作り方があるかを返す。
    dp[i][n][s]: qs[:i] までを合計n個使って合計sとなる組み合わせの数
    qs[i] = qi とすると
    dp[i + 1][0][0] = 1
    dp[i + 1][0][s] = 0, s > 0
    dp[i + 1][1][s] = 1 if s == qi else dp[i][1][s]
    dp[i + 1][n][s] = dp[i][n][s] + dp[i + 1][n - 1][s - qi]
    [i] を落とすと、
    dp[n][s] += dp[n-1][s-n] で更新する。
    '''
    len_dp = qs[-1] * Q + 1
    dp = [[0] * len_dp for n in range(Q + 1)]
    dp[0][0] = 1
    for q in qs:
        for n in range(1, Q + 1):
            current_dp = dp[n]
            prev_dp = dp[n - 1]
            for s in range(q, q * n + 1):
                current_dp[s] += prev_dp[s - q]
    return dp[Q]


def merge_dists(distp, distc):
    mod = 10 ** 9 + 7
    len_p = len(distp)
    len_c = len(distc)
    dist = [0] * (len_p + len_c - 1)
    for i, pi in enumerate(distp):
        for ij, cj in enumerate(distc, i):
            dist[ij] += pi * cj
            dist[ij] %= mod
    return dist


def get_mat(dist):
    n = len(dist)
    mat = [dist[:]]
    for i in range(n - 1):
        row = [0] * n
        row[i] = 1
        mat.append(row)
    return mat


def mult(mat1, mat2, mod):
    nrow = len(mat1)
    ncol = len(mat2[0])
    mat = [[0] * ncol for r in range(nrow)]
    for c in range(ncol):
        col2 = [row[c] for row in mat2]
        for r, row1 in enumerate(mat1):
            mat[r][c] = sum(a * b for a, b in zip(row1, col2)) % mod
    return mat


def get_identity_matrix(n):
    matI = [[0] * n for i in range(n)]
    for i in range(n):
        matI[i][i] = 1
    return matI
    

def matrix_pow(mat, p, mod):
    n = len(mat)
    matR = get_identity_matrix(n)
    while p:
        if p & 1: matR = mult(mat, matR, mod)
        mat = mult(mat, mat, mod)
        p >>= 1
    return matR


def finalize(mat, dist, mod):
    n = len(dist)
    vec = [[0] for i in range(n)]
    vec[0][0] = 1
    vec_n = mult(mat, vec, mod)
    result = 0
    for i, v_row in enumerate(vec_n):
        result += sum(dist[i:]) * v_row[0]
        result %= mod
    return result

def print_mat(mat):
    for row in mat:
        print(row)

if __name__ == '__main__':
    N, P, C = map(int, input().split())
    print(solve(N, P, C))
0