5195. 【NOIP2017提高组模拟7.3】A
Time Limits:
1000 ms Memory Limits: 262144 KB Detailed Limits
Goto ProblemSet
做法:类似第二类????????????????????????????????数的,我们将方案分成两种: 1.至少包含一个 1 的;2.一个 1 都不包含。 设????[????][????]表示答案,那么表示1.的答案即为????[???? − 1][???? − 1],表示2.的答案 即为????[???? − ????][????](相当于把每个数都加上1),所以有: ????[????][????] = ????[???? − 1][???? − 1] + ????[???? − ????][????],时间O(????????)。
代码如下:
View Code
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 }