InputThere might be multiple test cases, no more than 5. You need to read till the end of input.
For each test case, a line containing four integers n,m,A,B.
1≤n,m,A,B≤3000 1≤n,m,A,B≤3000
.
OutputFor each test case, output a line containing the answer modulo 998244353.
Sample Input
3 4 1 2
Sample Output
169
题意：给N*M的空白格子染色，求至少x行，至少y列被染色的方案数。
思路：不会，占位。
#include<bits/stdc++.h> using namespace std; #define LL long long const int maxn = 3001; const int MOD = 998244353; int n, m, A, B, ans; int C[maxn][maxn], two[maxn * maxn]; int fa[maxn], fb[maxn]; void Init() { for(int i = 0; i < maxn; ++i) { for(int j = 0; j <= i; ++j) { if(j == i || j == 0) { C[i][j] = 1; } else { C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; if(C[i][j] >= MOD) { C[i][j] -= MOD; } } } } two[0] = 1; for(int i = 1; i < maxn * maxn; ++i) { two[i] = two[i - 1] * 2; if(two[i] >= MOD) { two[i] -= MOD; } } } int main() { Init(); while(~scanf("%d%d%d%d", &n, &m, &A, &B)) { ans = 0; for(int i = A; i <= n; ++i) { fa[i] = 0; for(int j = A; j < i; ++j) { fa[i] = (fa[i] + (LL)C[i][j] * fa[j]) % MOD; } fa[i] = 1 - fa[i]; if(fa[i] < 0) { fa[i] += MOD; } } for(int i = B; i <= m; ++i) { fb[i] = 0; for(int j = B; j < i; ++j) { fb[i] = (fb[i] + (LL)C[i][j] * fb[j]) % MOD; } fb[i] = 1 - fb[i]; if(fb[i] < 0) { fb[i] += MOD; } } for(int i = A; i <= n; ++i) { LL tmp = (LL)fa[i] * C[n][i] % MOD; for(int j = B; j <= m; ++j) { ans = (ans + ((tmp * fb[j] % MOD) * C[m][j] % MOD) * two[(n - i) * (m - j)] % MOD) % MOD; } } printf("%d\n", ans); } return 0; }
原文：https://www.cnblogs.com/hua-dong/p/9851697.html
