2021 Shanghai sai-d-cartland number variant, DP

The main idea of the topic :

Here you are. $n$ Number , Let you divide into two rows with a length of n/2 Array of $a_i,b_i$. Then make the two arrays orderly and $a_i\le b_i$.
$n\le 5e3$

Topic ideas :

If the number is different , It's a Cartland number . Duplicate number , need dp Calculation .

First consider how $dp$ Ask for two different situations :
Convert it into a sequence of parentheses . The first row is regarded as the subscript of the left bracket , The second row shows the subscript of the right bracket .
The number of left parentheses in any prefix state shall not be less than the number of right parentheses .

such $dp(i,j)$ For the former i Number , There are more left parentheses than right parentheses j Number of projects .

Consider the same situation : Just enumerate from small to large according to the type of number . Enumerate one more < Put several numbers on it >. When transferring, multiply by a factorial .

Because it's put like this , The two methods must correspond to different distributions of this number , So step by step multiplication , Multiply by factorial

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
const int maxn = 5e3 + 5;
const int mod = 998244353;
int a[maxn];
ll dp[maxn][maxn] , f[maxn];
unordered_map<int,int> s;
int main()
{
    
    f[0] = 1;
    for (int i = 1 ; i < maxn ; i++)
        f[i] = f[i - 1] * i % mod;
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1 ; i <= n ; i++){
    
        cin >> a[i];
        s[a[i]]++;
    }
    sort(a + 1 , a + 1 + n);
    int m = unique(a + 1 , a + 1 + n) - a - 1;
    dp[0][0] = 1;
    for (int i = 1 ; i <= m ; i++){
    
        for (int j = 0 ; j <= n ; j++){
    
            int num = s[a[i]];
            for (int k = 0 ; k <= num ; k++){
    
                int l = j - 2 * k + num;
                if (l < 0) continue;
                dp[i][j] = (dp[i][j] + dp[i - 1][l] * f[num] % mod) % mod;
            }
        }
    }
    cout << dp[m][0] << endl;
    return 0;
}