Little Tiger vs. Deep Monkey

/*
f[i][j]:表示猴子做前i道题得j分的概率
    ①:f[i + 1][j + arr[i + 1]] += f[i][j] * 0.5
    ②:f[i + 1][j] += f[i][j] * 0.5
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50;

int arr[N];
double f[N][40010];
int n;
double p;

int main() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%lf", &n, &p);
        int sum = 0;
        for (int i = 1; i <= n; i ++) {
            scanf("%d", &arr[i]);
            sum += arr[i];
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1.0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j <= sum - arr[i + 1]; j ++ )
                if (f[i][j]) {
                    f[i + 1][j + arr[i + 1]] += f[i][j] * 0.5;
                    f[i + 1][j] += f[i][j] * 0.5;
                }
        double s = 0;
        for (int i = 0; i <= sum; i ++ ) {
            s += f[n][i];
            if (s >= p) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}

Rikka with Nash Equilibrium

/*
f[k][i][j]:确定了i行、j列的组合数量
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 90;

typedef long long LL;

LL f[2][N][N];
int n, m, k;

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d%d%d", &n, &m, &k);
        int cur = 1;
        memset(f, 0, sizeof f);
        f[cur][1][1] = n * m % k;

        for (int pos = 1; pos < n * m; pos ++ ) {

            cur ^= 1, memset(f[cur], 0, sizeof f[cur]);

            for (int i = 1; i <= n; i ++ )

                for (int j = 1; j <= m; j ++ ) {

                    if (pos > i * j)
                        continue;
                    f[cur][i + 1][j] += (n - i) * j * f[cur ^ 1][i][j] % k;
                    f[cur][i + 1][j] %= k;
                    f[cur][i][j + 1] += (m - j) * i * f[cur ^ 1][i][j] % k;
                    f[cur][i][j + 1] %= k;
                    f[cur][i][j] += (i * j - pos) * f[cur ^ 1][i][j] % k;
                    f[cur][i][j] %= k;
                }
        }

        printf("%lld\n", f[cur][n][m]);
    }

    return 0;
}

Wavel Sequence

/*
f[j][0]:以b序列第j结尾为谷底的波浪满足的次数。
f[j][1]:以b序列第j结尾为谷峰的波浪满足的次数。
sum[j][0]:以b序列第j结尾为谷底的波浪满足的“总”次数。
sum[j][1]:以b序列第j结尾为谷峰的波浪满足的“总”次数。
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, mo = 998244353;

typedef long long LL;

int n, m, a[N], b[N];
LL sum[N][2], f[N][2];

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; i ++ )

            scanf("%d", &a[i]);

        for (int i = 1; i <= m; i ++ )

            scanf("%d", &b[i]);
        memset(sum, 0, sizeof sum);
        LL ans = 0;

        for (int i = 1; i <= n; i ++ ) { // f数列的尾部

            int cnt1 = 1, cnt2 = 0; // 谷底本身就是答案的一种

            for (int j = 1; j <= m; j ++ ) { // g数列的尾部

                f[j][0] = f[j][1] = 0; // 初始化每次的寻找

                if (a[i] == b[j]) {
                    f[j][0] += cnt1;
                    f[j][0] %= mo;
                    f[j][1] += cnt2;
                    f[j][1] %= mo;
                    ans += cnt1 + cnt2;
                    ans %= mo;
                } else if (a[i] > b[j]) {
                    cnt2 += sum[j][0];
                    cnt2 %= mo;
                } else {
                    cnt1 += sum[j][1];
                    cnt1 %= mo;
                }
            }

            for (int j = 1; j <= m; j ++ )

                if (a[i] == b[j]) {
                    sum[j][0] += f[j][0];
                    sum[j][0] %= mo;
                    sum[j][1] += f[j][1];
                    sum[j][1] %= mo;
                }
        }

        printf("%lld\n", ans);
    }

    return 0;
}

度度熊看球赛

/*
f[i][j]:已有i对情侣入座，j对情侣坐在一起的方案数。
    ①:第i对情侣分开坐
        1.1 没拆散
        1.2 只有一个人拆散一对
        1.3 一人拆散一对
    ②:第i对情侣并排坐
        2.1 两人共同拆散一对
        2.2 把之前的（j-1）对情侣看成一团，放在他们的间隙插空坐
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1010;
const LL mo = 998244353;

int n, d;
int f[N][N], p[N];

void init_p() {
    p[0] = 1; // 2^0

    for (int i = 1; i < N; i ++ )

        p[i] = 1LL * p[i - 1] * 2 % mo;
}

void init_f() {
    f[0][0] = 1;

    for (int i = 0; i < 1000; i ++ )

        for (int j = 0; j <= i; j ++ ) {

            LL tmp = 2 * i - j + 1; // 当前的空位置个数
            //
            f[i + 1][j] += 1LL * f[i][j] * j % mo;
            f[i + 1][j] %= mo;
            // 把之前的（j-1）对情侣看成一团，放在他们的间隙插空坐
            f[i + 1][j + 1] += 1LL * f[i][j] * tmp % mo;
            f[i + 1][j + 1] %= mo;

            if (j - 2 >= 0) { // 一人拆散一对
                f[i + 1][j - 2] += 1LL * f[i][j] * (j * (j - 1) / 2) % mo;
                f[i + 1][j - 2] %= mo;
            }

            // 只有一个人拆散一对
            if (j - 1 >= 0) {
                f[i + 1][j - 1] += 1LL * f[i][j] * j % mo * tmp % mo;
                f[i + 1][j - 1] %= mo;
            }

            // 没拆散
            f[i + 1][j] += 1LL * f[i][j] * (tmp * (tmp - 1) / 2) % mo;
            f[i + 1][j] %= mo;
        }
}

int main() {
    init_p();
    init_f();

    while (~scanf("%d%d", &n, &d)) {

        int ans = 0;
        int temp = 1;

        for (int i = 0; i <= n; i ++ ) {

            ans = (ans + 1LL * f[n][i] % mo * temp % mo * p[n] % mo) % mo;
            temp = 1LL * temp * d % mo;
        }

        printf("%d\n", ans);
    }

    return 0;
}