Edit

【pythonでABC178を解説】D - Redistribution

問題概要

問題ページ

問題文

整数 \(S\) が与えられます。
すべての項が \(3\) 以上の整数で、その総和が \(S\) であるような数列がいくつあるか求めてください。ただし、答えは非常に大きくなる可能性があるので、 \(10^9+7\) で割った余りを出力してください。

制約

  • \(1 \leq S \leq 2000\)
  • 入力はすべて整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = int(input().rstrip('\n'))
    dp = [[0] * (s + 1) for _ in range(s + 1)]
    total = 0
    for i in range(s + 1):
        if i == 0:
            for j in range(3, s + 1):
                dp[i][j] = 1
        else:
            acm = 0
            for j in range(3 * (i + 1), s + 1):
                acm += dp[i-1][j-3]
                acm %= mod
                dp[i][j] = acm
        total += dp[i][-1]
    print(total % mod)


if __name__ == '__main__':
    solve()

プログラミング

-Edit
-