题目描述

In the most popular card game in Berland, a deck of $n \times m$ cards is used. Each card has two parameters: suit and rank. Suits in the game are numbered from $1$ to $n$, and ranks are numbered from $1$ to $m$. There is exactly one card in the deck for each combination of suit and rank.

A card with suit $a$ and rank $b$ can beat a card with suit $c$ and rank $d$ in one of two cases:

• $a = 1$, $c \ne 1$ (a card of suit $1$ can beat a card of any other suit);
• $a = c$, $b > d$ (a card can beat any other card of the same suit but of a lower rank).

Two players play the game. Before the game starts, they receive exactly half of the deck each. The first player wins if for every card of the second player, he can choose his card that can beat it, and there is no card that is chosen twice (i. e. there exists a matching of the first player’s cards with the second player’s cards such that in each pair the first player’s card beats the second player’s card). Otherwise, the second player wins.

Your task is to calculate the number of ways to distribute the cards so that the first player wins. Two ways are considered different if there exists a card such that in one way it belongs to the first player and in the other way it belongs to the second player. The number of ways can be very large, so print it modulo $998244353$.

Input

The only line contains two integers $n$ and $m$ ($1 \le n, m \le 500$).

Additional constraint on the input: $m$ is even.

Output

Print a single integer — the number of ways to distribute the cards so that the first player wins, taken modulo $998244353$.

Example
input

1 4

output

2

input

500 500

output

84693741

思路
$n,m$都小于等于$500$，一眼dp
然后仔细研究题面，发现实际上是一种括号匹配，只是由于有1大于其他花色的条件，除了1以外的n-1个花色，你自己所拥有的前括号可以比对手所拥有的后括号要少
例如：())) 少了一个前括号，可以用一个1来替代
然后我们需要知道一行
我们用$f[i][j]$来表示 选到这一行的第$i$个数，其中对手选的数比自己选的数要多$j$个 的方案数
然后我们可以：
当前数为 对手选择 则：$$f[i][j]+=f[i-1][j-1]$$
当前数为 自己选择 则：$$f[i][j]+=f[i-1][j+1]$$

于是就得到了一行的方案数

我们用$dp[i][j]$表示枚举到第i个花色，对手比自己多选了j张牌
接着每一行进行枚举
$$dp[i][j - k]+=dp[i-1][j]*f[m][k]$$
上一行对手比自己多了j张牌，那么这一行的对手比自己多j-k张牌，就需要(上一行对手比自己多了j张牌的方案数)*(这一行选k个自己的牌的方案数)
最后$dp[n][0]$就是答案

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 998244353;
#define int long long
void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> f(m + 1, vector<int>(m + 1));
  f[0][0] = 1;
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j <= m; j++) {
      if (j) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % M;

      if (j < m) f[i][j] = (f[i][j] + f[i - 1][j + 1]) % M;
    }
  }

  vector<vector<int>> dp(n + 1, vector<int>(m + 1));

  for (int i = 0; i <= m; i ++) dp[1][i] = f[m][i];

  for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= j; k ++) {
        dp[i][j - k] = (dp[i][j - k] + dp[i - 1][j] * f[m][k] % M) % M;
      }
    }
  }
  cout << dp[n][0] << "\n";
}

signed main() {
  int _ = 1;
  while (_--) {
    solve();
  }
  return 0;
}