题目
解题思路动态规划
我们可以将方案分成两种：
至少包含一个
1
1
1 的；一个
1
1
1 都不包含。
设
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示答案，那么表示
1
1
1的答案即为
f
[
i
−
1
]
[
j
−
1
]
f[i-1][j-1]
f[i−1][j−1]，表示
2
2
2的答案即为
f
[
i
]
[
j
−
1
]
f[i][j-1]
f[i][j−1](相当于把每个数都加上
1
1
1)，所以有：，时间
O
(
n
k
)
O(nk)
O(nk)。
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#define rr register
using namespace std
;
const long long mod
=998244353;
long long n
,m
,f
[6005][6005];
signed main()
{
scanf("%lld%lld",&n
,&m
);
f
[0][0]=1;
for (rr
long long i
=1;i
<=m
;i
++)
for (rr
long long j
=i
;j
<=n
;j
++)
f
[i
][j
]=(f
[i
-1][j
-1]+f
[i
][j
-i
])%mod
;
printf("%lld",f
[m
][n
]);
}
