JZOJ 5195. 【NOIP2017提高组模拟7.3】A

5195. 【NOIP2017提高组模拟7.3】A 

Time Limits:  1000 ms  Memory Limits: 262144 KB  Detailed Limits  

Goto ProblemSet

Description

 

Input

Output

 

Sample Input

7 3

Sample Output

4

 

Data Constraint

 

做法：类似第二类????????????????????????????????数的，我们将方案分成两种： 1.至少包含一个 1 的；2.一个 1 都不包含。 设????[????][????]表示答案，那么表示1.的答案即为????[???? − 1][???? − 1]，表示2.的答案 即为????[???? − ????][????](相当于把每个数都加上1)，所以有： ????[????][????] = ????[???? − 1][???? − 1] + ????[???? − ????][????]，时间O(????????)。

 

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#define mo 998244353
using namespace std;
int n, k;
long long f[5007][5007];

void Dp()
{
    for (int i = 1; i <= n; i++)
    {
        f[i][1] = 1;
        for (int j = 2; j <= k; j++)
        {
            f[i][j] = f[i - 1][j - 1];
            if (i > j)    f[i][j] += f[i - j][j];
            f[i][j] %= mo;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    Dp();
    printf("%lld", f[n][k]);
}