牛客练习赛64 D 宝石装箱 （背包dp，容斥，数学）

题目：传送门

题意

 

 思路

官方题解：地址

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x) & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

const LL mod = 998244353;

LL ksm(LL a, LL b) {

    LL res = 1LL;

    while(b) {

        if(b & 1) res = res * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return res;

}

LL f[N], a[N], dp[N];

void solve() {

    int n, x;

    scanf("%d", &n);

    rep(i, 1, n) {

        scanf("%d", &x);

        a[x]++;

    }

    f[0] = 1LL;

    rep(i, 1, n) {

        f[i] = f[i - 1] * i % mod;

    }

    dp[0] = 1LL;

    rep(i, 1, n) {

        dep(j, 0, i - 1) {

            dp[j + 1] = (dp[j + 1] + dp[j] * a[i] % mod) % mod;

        }

    }

    LL p = 1;

    LL ans = 0LL;

    rep(i, 0, n) {

        ans = (ans + p * dp[i] * f[n - i] % mod + mod) % mod;

        p = -p;

    }

    printf("%lld
", ans);

}


int main() {

//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}