题解 | 小圆前辈的暴力枚举
小圆前辈的暴力枚举
https://ac.nowcoder.com/acm/contest/15332/I
小圆前辈的暴力枚举
思路:
或者排列组合,这里选择
求解
设
为行为
列为
的方案数目
初始化:
- 当仅有
行或
列时,方案数明显是全不放+每个格子放一次,即
种可能
- 当仅有
即 :
,其中
否则,对于有
行
列的格子而言:
- 选择最后一行,有
种选法(即每个格子选一边,但是仅能选一个),选择一个后,剩下能放的格子,除去本行、列外,还有
行
列
- 不选择最后一行:即为选取
行
列的方案数
- 选择最后一行,有
所以:
,记得取模即可
#include <bits/stdc++.h> #define endl '\n' typedef long long ll; typedef unsigned long long ull; using namespace std; const int mod = 998244353; ll dp[1007][1007]; signed main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; ++i) dp[i][1] = i + 1; for(int i = 1; i <= m; ++i) dp[1][i] = i + 1; for(int i = 2; i <= n; ++i) { for(int j = 2; j <= m; ++j ) { dp[i][j] = ( j * dp[i-1][j-1] % mod + dp[i-1][j] ) % mod; } }cout << dp[n][m] << endl; return 0; }