# 题解 P6017 【[CSGRound3]仙人掌】

### 做法5：

$f(n)=\lbrack n \mod 2=0 \rbrack (\frac{3}{2}n-2)+\lbrack n \mod 2=1\rbrack (\frac{3}{2}(n-1))$

### Code

#include <cstdio>
#include <algorithm>
#define mo 998244353
using namespace std;
int C[5005][5005];
bool check(int n, int m, int a, int b) {
if (m == n - 1)
return 1;
if (a > b)
m -= a, n -= a;
else
m -= (a + b) >> 1, n -= (a + b) >> 1;
if (m < n)
return 0;
if (m > (n - 1) / 2 * 3 + (n - 1) % 2)
return 0;
return 1;
}
int main() {
int cas;
scanf("%d", &cas);
C[0][0] = 1;
for (int i = 1; i <= 5000; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;
}
while (cas--) {
int n, m;
scanf("%d%d", &n, &m);
if (m > (n - 1) / 2 * 3 + (n - 1) % 2) {
puts("0");
continue;
}
if (n == 1) {
puts("0");
continue;
}
if (n == 2) {
if (m == 1)
puts("1");
else
puts("0");
continue;
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n - i; j++) {
if (i + j * 3 > m + m)
continue;
if (!check(n, m, i, j))
continue;
int m1 = m + m - i - j, n1 = n - i;
if (m1 & 1)
continue;
ans = ((long long)C[m1 / 2 - 1][n1 - 1] * C[n][n1] % mo * C[n1][j] + ans) % mo;
}
}
printf("%d\n", ans);
}
return 0;
}

2020-01-31 09:31:33 in 题解