結果

問題 No.997 Jumping Kangaroo
コンテスト
ユーザー LyricalMaestro
提出日時 2026-07-04 02:36:34
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 319 ms / 2,000 ms
コード長 2,735 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 165 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 81,280 KB
最終ジャッジ日時 2026-07-04 02:36:39
合計ジャッジ時間 3,584 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/286

MOD = 10 ** 9 + 7

def prod_vector(matrix, vector):
    n = len(matrix)
    new_vector = [0] * n
    for i in range(n):
        for j in range(n):
            new_vector[i] += (matrix[i][j] * vector[j]) % MOD
            new_vector[i] %= MOD
    return new_vector

def prod_matrix(left, right):
    n = len(left)
    new_matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                new_matrix[i][j] += (left[i][k] * right[k][j]) % MOD
                new_matrix[i][j] %= MOD
    return new_matrix

def main():
    N, W, K = map(int, input().split())
    A = list(map(int, input().split()))

    # matrixの計算

    matrix = [[0] * (2 * (W + 1)) for _ in range(2 * (W + 1))]

    for start_d in range(W):
        for start_state in range(2):
            if start_d == 0 and start_state == 1:
                continue

            dp = [[0] * (2 * W + 1) for _ in range(2)]
            dp[start_state][start_d] = 1

            for w in range(start_d, W):
                # state = 0
                for a in A:
                    if w + a < W:
                        dp[0][w + a] += dp[0][w]
                        dp[0][w + a] %= MOD
                    elif w + a == W or w + a == 2 * W:
                        dp[0][w + a] += dp[0][w]
                        dp[0][w + a] %= MOD
                    elif W < w + a < 2 * W:
                        dp[1][w + a] += dp[0][w]
                        dp[1][w + a] %= MOD
                
                # state = 1
                for a in A:
                    if w + a < W:
                        dp[1][w + a] += dp[1][w]
                        dp[1][w + a] %= MOD
                    elif w + a == W:
                        dp[0][w + a] += dp[1][w]
                        dp[0][w + a] %= MOD
            
            from_i = (W + 1) * start_state + start_d
            for to_i in range(2 * (W + 1)):
                state = to_i // (W + 1)
                w = to_i % (W + 1)
                matrix[to_i][from_i] = dp[state][w + W]
    matrix[0][W] = 1

    vector = [0] * (2 * (W + 1))
    vector[0] = 1
    K0 = K - 1    
    while K0 > 0:
        if K0 % 2 == 1:
            vector = prod_vector(matrix, vector)
        
        matrix = prod_matrix(matrix, matrix)
        K0 //= 2

    # 最後のdp
    dp = [0] * (W + 1)
    for i in range(2 * (W + 1)):
        w = i % (W + 1)
        dp[w] += vector[i]
        dp[w] %= MOD

    for j in range(W + 1):
        for a in A:
            if j + a <= W:
                dp[j + a] += dp[j]
                dp[j + a] %= MOD
    
    print(dp[-1])



            





if __name__ == '__main__':
    main()
0