【競技プログラミング】AtCoder Beginner Contest 248_C問題

# 問題
https://atcoder.jp/contests/abc248/tasks/abc248_c

## 要約
1. 長さNの整数列A = (A1, ..., AN)を考える。

2. 以下の条件を満たす数列の個数を求める
   a. 各要素Aiは1以上M以下の整数（1 ≤ i ≤ N）。
   b. 数列の要素の合計がK以下（A1 + A2 + ... + AN ≤ K）。

3. 答えが非常に大きくなる可能性があるため、998244353で割った余りを求める。

- N: 数列の長さ
- M: 各要素の最大値
- K: 数列の要素の合計の上限
- Ai: 数列の各要素（1 ≤ Ai ≤ M）


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

# アプローチ
動的計画法を用いて、条件を満たす数列の個数を計算する。
二次元のDPテーブルを使用し、数列の長さと要素の合計を考慮しながら、可能な組み合わせの数を累積的に計算する。


# 解法手順

1. 入力値N, M, Kを受け取る。

2. (N+1) × (K+1)の二次元配列dpを作成し、初期値を0で埋める。

3. dp[0][0]を1に設定する（長さ0で合計0の数列は1通り）。

4. 以下のループを実行する：
   a. 数列の長さiを0からN-1まで繰り返す。
   b. 現在の合計jを0からK-1まで繰り返す。
   c. 追加する要素lを1からMまで繰り返す。
   d. j+l ≤ Kの場合、dp[i+1][j+l] += dp[i][j]を実行する。

5. dp[N][1]からdp[N][K]までの値を合計し、答えとする。

6. 答えをmod（998244353）で割った余りを計算する。

7. 最終的な答えを出力する。


# ACコード
```python:ac.py
# モジュロ演算の基数
mod = 998244353

def io_func():
    # 入力値N, M, Kを受け取る
    return map(int, input().split())

def solve(n, m, k):
    # (N+1) × (K+1)の二次元配列dpを作成し、初期値を0で埋める
    dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
    
    # dp[0][0]を1に設定する（長さ0で合計0の数列は1通り）
    dp[0][0] = 1

    # 数列の長さiを0からN-1まで繰り返す
    for i in range(n):
        # 現在の合計jを0からK-1まで繰り返す
        for j in range(k):
            # 追加する要素lを1からMまで繰り返す
            for l in range(1, m+1):
                # j+l ≤ Kの場合、dp[i+1][j+l] += dp[i][j]を実行する
                if j + l <= k:
                    dp[i+1][j+l] += dp[i][j]

    # dp[N][1]からdp[N][K]までの値を合計し、答えとする
    ans = sum(dp[n][1:k+1])

    # 答えをmod（998244353）で割った余りを計算する
    ans %= mod

    # 最終的な答えを返す
    return ans

if __name__=="__main__":
    # メイン処理
    n, m, k = io_func()
    result = solve(n, m, k)
    print(result)

###
# n: 数列の長さ
# m: 各要素の最大値
# k: 数列の要素の合計の上限
# dp: 動的計画法のテーブル。dp[i][j]は長さiで合計jの数列の個数
# ans: 条件を満たす数列の総数

# 1. io_func関数: 標準入力から値を読み取る
# 2. solve関数: 動的計画法を用いて問題を解く
#    - dpテーブルの初期化
#    - 三重ループでdpテーブルを埋める
#    - 最終的な答えを計算し、モジュロ演算を適用
# 3. メイン処理: io_func関数で入力を受け取り、solve関数で結果を計算し、出力する
```

# 思考過程

数列の長さと要素の合計を考慮しながら、可能な組み合わせの数を累積的に計算する。

# 計算量の概算

(N * K * M)


# その他周辺知識
## 2次元リストの初期化
```python
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
```
これは2次元のリストを作成している。
- 外側のリスト内包表記：`[... for _ in range(n+1)]`で、n+1個の要素を持つリストを作成。
- 内側のリスト内包表記：`[0 for _ in range(k+1)]`で、各要素がk+1個の0を持つリストになる。
結果として、(n+1) × (k+1)の大きさの2次元リストが作成され、すべての要素が0で初期化される。


## 動的計画法（漸化式）

```python
for i in range(n):
    for j in range(k):
        for l in range(1, m+1):
            if j + l <= k:
                dp[i+1][j+l] += dp[i][j]
```

dp[i+1][j+l] += dp[i][j]という漸化式を用いて、より小さな部分問題の解から大きな問題の解を構築している。

ここで、
- i は現在の数列の長さ
- j は現在の数列の要素の合計
- l は新たに追加する要素の値
を表している。

例えば、dp[3][10]（長さ3で合計10の数列の個数）を計算する際、dp[2][7]、dp[2][8]、dp[2][9]などの値を利用する。
これは「長さ2で合計7の数列に3を追加する」「長さ2で合計8の数列に2を追加する」などの操作に対応している。

## 累積和

```python
ans = sum(dp[n][1:k+1])
```

最終的な答えを求める際、dp[n][1]からdp[n][k]までの値を合計している。



# エッセンス
```python:sample_code.py
def count_sequences(n, m, k, mod=998244353):
    """
    条件を満たす数列の組み合わせの数を計算する関数

    Parameters:
    n (int): 数列の長さ
    m (int): 各要素の最大値
    k (int): 数列の要素の合計の上限
    mod (int): モジュロ演算の基数 (デフォルト: 998244353)

    Returns:
    int: 条件を満たす数列の組み合わせの数（モジュロ mod）
    """
    # (N+1) × (K+1)の二次元配列dpを作成し、初期値を0で埋める
    dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
    
    # dp[0][0]を1に設定する（長さ0で合計0の数列は1通り）
    dp[0][0] = 1

    # 数列の長さiを0からN-1まで繰り返す
    for i in range(n):
        # 現在の合計jを0からK-1まで繰り返す
        for j in range(k):
            # 追加する要素lを1からMまで繰り返す
            for l in range(1, m+1):
                # j+l ≤ Kの場合、dp[i+1][j+l] += dp[i][j]を実行する
                if j + l <= k:
                    input(dp)
                    dp[i+1][j+l] = (dp[i+1][j+l] + dp[i][j]) % mod
                    input(dp)

    # dp[N][1]からdp[N][K]までの値を合計し、答えとする
    ans = sum(dp[n][1:k+1]) % mod

    return ans

if __name__=="__main__":
    # 使用例
    n = 3  # 数列の長さ
    m = 4  # 各要素の最大値
    k = 7  # 数列の要素の合計の上限

    result = count_sequences(n, m, k)
    print(f"条件を満たす数列の組み合わせの数: {result}")

    # カスタムのモジュロ基数を使用する場合
    custom_mod = 1000000007
    result_custom_mod = count_sequences(n, m, k, mod=custom_mod)
    print(f"カスタムモジュロを使用した結果: {result_custom_mod}")
```


# 動的計画法の補足
## 問題
が求めたいのは、条件を満たす数列の個数である。
この条件とは：
- 数列の長さがN
- 各要素が1以上M以下
- 数列の要素の合計がK以下

## 動的計画法の考え方

- 長さNの数列の個数を求めるためには、長さN-1の数列の個数が分かっていればよい。
- そのため、DPテーブルをdp[i][j]のように作り、iを数列の長さ、jを数列の要素の合計とする。
- dp[i][j]は、長さiで合計jの数列の個数を表す。

## DPテーブルの構築
- 初期状態: dp[0][0] = 1 （長さ0で合計0の数列は1通り）
- dp[i+1][j+l] += dp[i][j] （長さiで合計jの数列に、要素lを追加）

## 計算の流れ:
- 数列の長さiを0からN-1まで増やす。
- 各長さiに対して、現在の合計jを0からK-1まで考える。
- 各(i, j)の組み合わせに対して、新たに追加する要素lを1からMまで試す。
- j+l ≤ Kの場合、dp[i+1][j+l]にdp[i][j]を加算する。

## 最終的な答え:
- dp[N][1]からdp[N][K]までの値を合計すると、条件を満たす数列の総数が得られる。

## 、例えばN=3, M=2, K=4の場合

```
dp[0]: [1, 0, 0, 0, 0]
dp[1]: [0, 1, 1, 0, 0]
dp[2]: [0, 0, 1, 2, 1]
dp[3]: [0, 0, 0, 1, 3]
```

最終的な答えは、dp[3][1] + dp[3][2] + dp[3][3] + dp[3][4] = 0 + 0 + 1 + 3 = 4 となる。