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

时间:2022-02-13 10:18:35

Description

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

Input

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

Output

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

Sample Input

7 3

Sample Output

4
 

Data Constraint

JZOJ 5195. 【NOIP2017提高组模拟7.3】A
 
做法:类似第二类????????????????????????????????数的,我们将方案分成两种: 1.至少包含一个 1 的;2.一个 1 都不包含。 设????[????][????]表示答案,那么表示1.的答案即为????[???? − 1][???? − 1],表示2.的答案 即为????[???? − ????][????](相当于把每个数都加上1),所以有: ????[????][????] = ????[???? − 1][???? − 1] + ????[???? − ????][????],时间O(????????)。
 
代码如下:
JZOJ 5195. 【NOIP2017提高组模拟7.3】AJZOJ 5195. 【NOIP2017提高组模拟7.3】A
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #define mo 998244353
 5 using namespace std;
 6 int n, k;
 7 long long f[5007][5007];
 8 
 9 void Dp()
10 {
11     for (int i = 1; i <= n; i++)
12     {
13         f[i][1] = 1;
14         for (int j = 2; j <= k; j++)
15         {
16             f[i][j] = f[i - 1][j - 1];
17             if (i > j)    f[i][j] += f[i - j][j];
18             f[i][j] %= mo;
19         }
20     }
21 }
22 
23 int main()
24 {
25     scanf("%d%d", &n, &k);
26     Dp();
27     printf("%lld", f[n][k]);
28 }
View Code