ABC 248 C - Dice Sum（DP：背包）

https://atcoder.jp/contests/abc248/tasks/abc248_c

题目大意：

给定长度为n，可选择的数字的范围【1，m】,放置的数字的总和不能超过k；

问我们能凑出多少种不同的情况？取模。

Sample Input 1
2 3 4
Sample Output 1 
6

Sample Input 2 
31 41 592
Sample Output 2
798416518

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2522;
const LL mod=998244353;
LL f[100][M];
//f[i][j]表示前i个数字,总数为j
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n,m,k;//长度，范围，最大总和
        cin>>n>>m>>k;
        
        LL res=0;
        f[0][0]=1;//长度为0，总和为0的时候，只有一种情况
        
        for(LL i=1;i<=n;i++)//长度
        {
            for(LL j=0;j<=k;j++)//可以凑出的总和
            {
                for(LL last=1;last<=m;last++)//区间选择
                {
                    //如果当前选择的数字都会比总和更小的话，那么我们就一定可以前面由一些数字给他凑出来（即使为0）
                    //位数减去一，并且总数减去这一个last那么就可以拼凑出现在的总和

                    //如果我要凑出的总和大于这个数字的话，那么我们就可以往前寻找可以凑出来的可能性
                    if(j>=last) f[i][j]=(f[i][j]+f[i-1][j-last])%mod;//可以添加这位数字
                }
            }
        }
        for(LL j=0;j<=k;j++)//把相同的长度下，总和为不同的数字的情况都加起来
            res=(res+f[n][j])%mod;
        cout<<res<<endl;
    }
    return 0;
}