Educational Codeforces Round 116 (Rated for Div. 2) E. Arena(dp)

傳送門

題意：

對于一個陣列 a a a? ,假如當前有 c n t cnt cnt? 個 a i a_i ai?? 大于 0 0 0，那么一回合后，所有大于 0 0 0 的 a i a_i ai? 都會減去 c n t ? 1 cnt-1 cnt?1 ,假如經過幾回合后，只剩下一個數大于 0 0 0，則游戲結束，且存在勝者，反之則不存在勝者，求有多少陣列 a a a滿足游戲結束時不存在勝者，

題解：

設 d p [ i ] [ j ] dp[i][j] dp[i][j]表示陣列有 i i i 個數，且所有數都是小于等于 j j j 的合法方案，

1. 1. 1.? 如果 i ? 1 ≥ j i-1 \geq j i?1≥j ,那么一回合之后，所有人都會死，不存在勝者，方案數為 j i j^i ji

2. 2. 2. 如果 i ? 1 < j i-1<j i?1<j ,列舉一回合之后還存活 k k k 個人，那么轉移為 d p [ i ] [ j ] + = d p [ k ] [ j ? i + 1 ] × C ( i , k ) × ( i ? 1 ) i ? k dp[i][j]+=dp[k][j-i+1]\times C(i,k) \times (i-1)^{i-k} dp[i][j]+=dp[k][j?i+1]×C(i,k)×(i?1)i?k

C ( i , k ) C(i,k) C(i,k)表示 i i i 個人里面選 k k k 個人存活，那么剩下 i ? k i-k i?k個人的血量就是 ≤ ( i ? 1 ) \leq (i-1) ≤(i?1) ,所以有 ( i ? 1 ) i ? k (i-1)^{i-k} (i?1)i?k ，

代碼：

#pragma GCC diagnostic error "-std=c++11"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 998244353;
const int MAXN = 2e5 + 5;
const int inf = 0x3f3f3f3f;
ll fac[MAXN];
ll dp[505][505];
ll e[505][505], base[505][505];
void cal()
{
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = fac[i - 1] * i % mod;
}
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)
            ans = ans * a % mod;
    return ans;
}

ll C(ll n, ll m)
{
    if (n < m)
        return 0;
    return fac[n] * qpow(fac[n - m] * fac[m] % mod, mod - 2) % mod;
}
int main()
{
    cal();
    for (int i = 1; i <= 500; i++) {
        for (int j = 0; j <= i; j++) {
            e[i][j] = C(i, j);
        }
    }
    for (int i = 1; i <= 500; i++) {
        for (int j = 0; j <= 500; j++) {
            base[i][j] = qpow(i, j);
        }
    }
    int n, x;
    cin >> n >> x;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= x; j++) {
            if (i - 1 >= j) {
                dp[i][j] = base[j][i];
            } else {
                for (int k = 2; k <= i; k++) {
                    dp[i][j] = (dp[i][j] + dp[k][j - i + 1] * base[i - 1][i - k] % mod * e[i][k] % mod) % mod;
                }
                dp[i][j] = (dp[i][j] + base[i - 1][i]) % mod;
            }
        }
    }
    cout << dp[n][x] << endl;
}