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;
}