Skip to content

2018 Multi-University Training Contest 9

Contents

A. Rikka with Nash Equilibrium

题意：

构造一个 n \cdot m 的矩阵，使得 [1, n \cdot m] 中每个数只出现一次，并且纳什均衡只出现一次。

思路：

从大到小的放置，每一个都可以拓展一行拓展一列或者放在已经拓展的行列焦点，用记忆化搜索或 dp 即可。

Code 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
ll p;
ll dp[81][81][81 * 81];

ll DFS(int x, int y, int z) {
    if (z >= n * m)
        return 1;
    if (dp[x][y][z] != -1)
        return dp[x][y][z];
    ll res = 0;
    if (x < n)
        res = (res + y * (n - x) % p * DFS(x + 1, y, z + 1)) % p;
    if (y < m)
        res = (res + x * (m - y) % p * DFS(x, y + 1, z + 1)) % p;
    if (x * y > z)
        res = (res + (x * y - z) * DFS(x, y, z + 1)) % p;
    dp[x][y][z] = res;
    return res;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %lld", &n, &m, &p);
        memset(dp, -1, sizeof dp);
        ll ans = DFS(1, 1, 1);
        ans = n * m % p * ans % p;
        printf("%lld\n", ans);
    }
    return 0;
}

B. Rikka with Seam

留坑。

C. Rikka with APSP

留坑。

D. Rikka with Stone-Paper-Scissors

题意：

每个人有三种牌：「石头、剪刀、布」。

询问第一个人赢第二个人的期望。

思路：

考虑每一次出牌的概率相同，那么答案就是：

\frac{\mbox{赢的情况种数 - 输的情况}}{\mbox{牌数}} 赢的情况种数输的情况牌数

那么所有赢输情况种类数就是：

\frac {a_1 *(b_2 - c_2) + b_1 * (c_2 - a_2) + c_1 * (a_2 - b_2)} {a + b + c}
Code 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll a1, b1, c1, a2, b2, c2;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld %lld %lld %lld %lld %lld", &a1, &b1, &c1, &a2, &b2, &c2);
        ll ans = a1 * (b2 - c2) + b1 * (c2 - a2) + c1 * (a2 - b2);
        if (ans % (a1 + b1 + c1) == 0) {
            ans /= a1 + b1 + c1;
            printf("%lld\n", ans);
        } else {
            int flag = 0;
            if (ans < 0) {
                ans = -ans;
                flag = 1;
            }
            ll ans2 = a1 + b1 + c1;
            ll GCD = gcd(ans, ans2);
            ans /= GCD;
            ans2 /= GCD;
            if (flag)
                printf("-");
            printf("%lld/%lld\n", ans, ans2);
        }
    }
    return 0;
}

E. Rikka with Rain

留坑。

F. Rikka with Spanning Tree

留坑。

G. Rikka with Treasure

留坑。

H. Rikka with Line Graph

留坑。

I. Rikka with Bubble Sort

留坑。

J. Rikka with Time Complexity

留坑。

K. Rikka with Badminton

题意：

四种人，一种人啥都没有，一种人有拍，一种人有球，一种人有拍有球，求方案数使得有两拍一球。

思路：

考虑三种选择方案：

  • 两个有拍 + 一个有球。
  • 两个有拍有球。
  • 一个有拍，一个有拍有球。

答案就是：

2^a \cdot 2^c \cdot (2^b - 1) \cdot (2^d - 1) + 2^a \cdot 2^c \cdot (2^d - 1 - d) + 2^a \cdot (2^b - 1 - b) \cdot (2^c - 1)
Code 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll MOD = 998244353;

ll qmod(ll n) {
    ll res = 1;
    ll base = 2;
    while (n) {
        if (n & 1)
            res = res * base % MOD;
        base = base * base % MOD;
        n >>= 1;
    }
    return res;
}

int t;
ll a, b, c, d;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        ll n = a + b + c + d;
        ll res = qmod(a) * qmod(c) % MOD * (qmod(b) - 1 + MOD) % MOD * (qmod(d) - 1 + MOD) % MOD;
        res = (res + qmod(a) * qmod(c) % MOD * (qmod(d) - 1 - d + MOD) % MOD) % MOD;
        res = (res + qmod(a) * (qmod(b) - 1 - b + MOD) % MOD * (qmod(c) - 1 + MOD)) % MOD;
        printf("%lld\n", (qmod(n) - res + MOD) % MOD);
    }
    return 0;
}
Last update: March 29, 2022
Created: March 29, 2022
Back to top