GYM 105322 A
题目描述
有 \(N\) 个人（\(N\) 为偶数），每次将随机分成 \(\frac{N}{2}\) 个 \(2\) 人组。组内两个人将进行比赛，每个人都有 \(\frac{1}{2}\) 的概率赢。赢得人排在前面。求一开始在排名 \(x\)，进行 \(k\) 轮比赛后的期望位置。
思路
很容易想到到达除了 \(x\) 以外的排名的概率都是一样的，所以我们定义 \(dp_{i,1/0}\) 表示进行 \(i\) 轮比赛，是/否在位置 \(x\) 的概率。
这两个状态都能互相转移，转移如下：
\[\begin{array}{l}
dp_{i,0}=dp_{i-1,0} \cdot (\frac{1}{2} + \frac{n - 2}{2(n - 1)}) + dp_{i-1,1}\cdot\frac{1}{2(n - 1)}\\
dp_{i,1} = dp_{i,0} \cdot \frac{1}{2} + dp_{i,1} \cdot \frac{1}{2}
\end{array}
\]
可以优化成矩阵形式：
\[\begin{bmatrix}dp_{i,0}\\dp_{i,1}\end{bmatrix}=\begin{bmatrix}dp_{i-1,0}\\dp_{i-1,1}\end{bmatrix}\begin{bmatrix}\frac{1}{2} + \frac{n - 2}{2(n - 1)} & \frac{1}{2(n - 1)}\\\frac{1}{2}&\frac{1}{2}\end{bmatrix}
\]
空间复杂度 \(O(1)\)，时间复杂度 \(O(\log k)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int MOD = 998244353, inv2 = 499122177;struct Matrix {int n, m, mat[3][3];void Clear(int a, int b) {n = a, m = b;for(int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) {mat[i][j] = 0;}}}Matrix operator*(const Matrix &x) {Matrix ret;ret.Clear(x.n, m);for(int i = 1; i <= x.n; ++i) {for(int j = 1; j <= m; ++j) {for(int k = 1; k <= n; ++k) {ret.mat[i][j] = (ret.mat[i][j] + 1ll * mat[k][j] * x.mat[i][k] % MOD) % MOD;}}}return ret;}Matrix operator*=(const Matrix &x) {return *this = *this * x;}
}mat, x;ll n, k, X;int Pow(int a, ll b) {int ret = 1;for(; b; a = 1ll * a * a % MOD, b >>= 1) {if(b & 1) {ret = 1ll * ret * a % MOD;}}return ret;
}Matrix Pow(Matrix ret, Matrix a, ll b) {for(; b; a *= a, b >>= 1) {if(b & 1) {ret *= a;}}return ret;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> X >> k;mat.Clear(2, 2);mat.mat[1][1] = (inv2 + 1ll * (n - 2) % MOD * Pow(2ll * ((n - 1) % MOD) % MOD, MOD - 2) % MOD) % MOD;mat.mat[1][2] = 1ll * inv2 * Pow((n - 1) % MOD, MOD - 2) % MOD;mat.mat[2][1] = mat.mat[2][2] = inv2;x.Clear(2, 1);x.mat[2][1] = 1;Matrix ans = Pow(x, mat, k);cout << (1ll * (1ll * (1 + n % MOD) % MOD * (n % MOD) % MOD * inv2 % MOD - (X % MOD) + MOD) % MOD * ans.mat[1][1] % MOD + 1ll * X % MOD * ans.mat[2][1] % MOD) % MOD;return 0;
}
GYM 105322 B
题目描述
有一个 \(N\) 个数的序列 \(A\)，两个人将轮流进行以下操作之一：
- 删除序列中其中一个最小值。
- 在所有数 \(>0\) 的情况下，你可以令所有元素减一。
求最终哪一方会赢。
思路
假设现在只有两个数，那么只要有一方删掉了较小值，那么另一方就赢了，所以两方一定会不断减一知道实在不能减为止。
现在我们将 \(A\) 排序。
在到达只有两个数的局面之前，一定会先删掉 \(N-2\) 个元素，而这里减法是将整个数组减一，所以我们不关心其顺序，总共会减 \(A_{N-1}\) 次。
只需判断次数的奇偶性即可。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int MAXN = 1000001;int n;
ll a[MAXN];int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) {cin >> a[i];}sort(a + 1, a + n + 1);if((a[n - 1] + n - 1) % 2 == 0) {cout << "Eric";}else {cout << "Cire";}return 0;
}
