题解：2024牛客暑期多校第5场——L [知]

英文题干

The game consists of n levels, and you know in advance the probability of passing each level, given as ,..., where are non-negative integers.

You can perform any number of operations. Each operation allows you to choose an index and decrement by one while incrementing by one.

After performing operations, you start the game, aiming to maximize the probability of passing all levels.

Output the maximum probability multiplied by modulo 998244353.

Input:

The first line contains a positive integer , indicating the number of test cases.For each test case:

The first line contains a positive integer .

The second line contains non-negative integers .

Output:

For each test case, output one non-negative integer, representing the result of the maximum probability multiplied by modulo 998244353.

中文题干

游戏由 n 关组成，您事先知道每一关通过的概率，表示为 , ...，其中 是非负整数。

您可以进行任意次数的操作。每次操作允许您选择一个索引 ，将 减少 1，同时将 增加 1。

在进行操作后，您开始游戏，目标是最大化通过所有关卡的概率。

思路

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 110;
const int mod = 998244353;

ll a[maxn];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        for (int i = 1; i <= n; i++) {
            while (1) {
                int pt = 1;
                for (int j = 1; j < i; j++) {
                    if (a[j] < a[pt]) {
                        pt = j;
                    }
                }

                if (a[pt] < a[i]) {
                    a[pt]++;
                    a[i]--;
                }
                else {
                    break;
                }
            }
        }

        ll ans = 1;
        for (int i = 1; i <= n; i++) {
            ans = (ans * a[i]) % mod;
        }
        cout << ans << endl;
    }
    
    return 0;
}