打得是第一场，赛时只做出了5题，rk50几，感觉不太行。
题目传送门
1, 2, 3, 5
十分简单，四道签到题，三道是二分。
6. 随机序列逆序数
题意
给定一个集合 $b$，大小为 $n$。
执行 $n$ 次操作。每次操作取出一个数。记此时集合中所有数之和为 $s$，则取出 $x$ 的概率为 $\dfrac{x}{s}$。取出后不再放回。
取出的数依次组成数列 $a$，求 $a$ 的逆序对数量的期望值$\mod 998244353$。
$n \le 10^6, b_i \le 10^5$
题解
考虑两个数 $x, y$ $(x<y)$ 形成逆序对的概率是多少。
设 $m$ 为第 $m$ 次操作前，$x,y$ 都没被取出，第 $m$ 次操作时，$x,y$ 中有一个被取出。那么 $y$ 在此时被取出的概率即为 $\dfrac{y}{x+y}$。因此问题的答案就是 $\sum\limits_{x<y} \dfrac{y}{x+y}$。
使用分治 NTT 解决。设 $c_i$ 为集合中 $i$ 的数量，在 $c$ 上进行分治。
合并时，把分母相同的放在一起算，即要求出 $\sum\limits_{x+y=s} y$。对于左边一半，$f_i=c_i$；对于右边一半，$g_i=c_i\cdot i$。这样 $f\cdot g$ 的第 $s$ 位即为所求。
Code
似乎卡常，递归的NTT无法通过，需要写非递归版。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| const int N = 1000006, mod = 998244353;
ll qpow(ll x, ll y) {
ll p = 1;
while (y) {
if (y & 1)p = p * x % mod;
x = x * x % mod;
y >>= 1;
}
return p;
}
int n, b[N], cnt = 0;
ll ans = 0;
ll f[N], g[N], c[N];
int re[N];
void NTT(ll *a, int lim) {
int k;
ll wn, w, t;
rep(i, lim) re[i] = (i & 1) * (lim >> 1) + (re[i >> 1] >> 1);
rep(i, lim) if(re[i] < i) swap(a[i], a[re[i]]);
for(int m = 2; m <= lim; m *= 2) {
k = m >> 1;
wn = qpow(3, (mod - 1) / m);
for(int i = 0; i < lim; i += m) {
w = 1;
rep(j, k) {
t = a[i + j + k] * w % mod;
a[i + j + k] = (a[i + j] - t + mod) % mod;
a[i + j] = (a[i + j] + t) % mod;
w = w * wn % mod;
}
}
}
}
void solve(int l, int r) {
if(l >= r) return;
int mid = (l + r) / 2;
solve(l, mid), solve(mid + 1, r);
int lim = 1;
while(lim <= mid - l + 1 || lim <= r - mid) lim *= 2;
lim *= 2;
rep(i, lim) f[i] = g[i] = 0;
rep(i, mid - l + 1) f[i] = c[l + i];
rep(i, r - mid) g[i] = c[mid + 1 + i] * (mid + 1 + i);
NTT(f, lim), NTT(g, lim);
rep(i, lim) f[i] = f[i] * g[i] % mod;
NTT(f, lim);
int inv = qpow(lim, mod - 2);
rep(i, lim) f[i] = f[i] * inv % mod;
reverse(f + 1, f + lim);
rep(i, lim) ans = (ans + f[i] * qpow(i + l + mid + 1, mod - 2)) % mod;
}
void Solve() {
cin >> n;
rep(i, n) cin >> b[i], c[b[i]]++;
n = 100000;
solve(1, n);
cout << ans;
}
|
7. 数字串
题意
给定一个 $n$ 位数 $s$，在其中添加恰好 $k$ 个加号，使得结果最大。输出这个最大的结果。
如 123 添加一个加号后可变成 1+23=24 或 12+3=15。
$k < n \le 10^6$
题解
显然应该要保留尽可能多的位数在一起，所以结果应该是一个 $n-k$ 位数加上 $k$ 个一位数。
此时问题变成寻找最大的 $n-k$ 位数，可使用后缀数组解决。
Code
其实就是SA模板。O3 优化后可以通过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| const int N = 2000006;
int n, k, m = N;
string s;
int rk[N], rk2[N], sa[N], id[N], cnt[N];
int st;
int ans[N];
void solve() {
cin >> n >> k >> s;
s = '-' + s;
repp(i, n)cnt[rk[i] = s[i]]++;
repp(i, m)cnt[i] += cnt[i - 1];
for (int i = n;i > 0;i--)sa[cnt[rk[i]]--] = i;
for (int len = 1;len <= n;len *= 2) {
init(cnt, 0);
repp(i, n)id[i] = sa[i];
repp(i, n)cnt[rk[id[i] + len]]++;
repp(i, m)cnt[i] += cnt[i - 1];
for (int i = n;i > 0;i--)sa[cnt[rk[id[i] + len]]--] = id[i];
init(cnt, 0);
repp(i, n)id[i] = sa[i];
repp(i, n)cnt[rk[id[i]]]++;
repp(i, m)cnt[i] += cnt[i - 1];
for (int i = n;i > 0;i--)sa[cnt[rk[id[i]]]--] = id[i];
memcpy(rk2, rk, sizeof(rk2));
int now = 0;
repp(i, n) {
if (rk2[sa[i]] == rk2[sa[i - 1]] && rk2[sa[i] + len] == rk2[sa[i - 1] + len])rk[sa[i]] = now;
else rk[sa[i]] = ++now;
}
}
repp(i, n) if(sa[i] <= k + 1) st = sa[i];
repp(i, n - k) ans[i] = s[st + i - 1] - '0';
repp(i, n) {
if(i < st || i >= st + n - k) {
int x = s[i] - '0';
int p = n - k;
ans[p] += x;
while(ans[p] >= 10) {
ans[p] %= 10;
p--;
ans[p] ++;
}
}
}
if(ans[0]) cout << ans[0];
repp(i, n - k) cout << ans[i];
}
|
8. 除法游戏
题意
有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。两人轮流操作，每次可以选择一堆石子（至少有 $2$ 个），然后平均分成若干堆。不能操作者判负。输出胜者为先手还是后手。
$n \le 5\cdot 10^4, a_i \le 10^{12}$
题解
可以首先发现的是，如果有偶数堆石子数量相同，那么其中一方必然可以复制另一方的操作，因此这几堆对胜负没有任何影响，可以直接删去。
若一堆石子为奇数个，则操作后必然分成奇数堆，于是可以删去除一堆外的所有。因此对一个奇数堆进行操作，实质上是将它除以一个因子。
若一堆石子为偶数个，则可分两种情况：若分为偶数个石子堆，则可将它们直接删去；若分为奇数堆。则删去除一堆外所有。因此对一个奇数堆进行操作，实质上是将它除以一个奇因子，或将直接删除。
于是可以转化为一个 Nim 游戏。一个数的每个奇质因子就相当于一个石子，除以一个奇因子就相当于拿走若干个石子。对于偶数，由于可以把所有奇因子除完后再通过一次操作把它删除，所以要多算一个石子。
因此我们要统计出所有数对应的石子数（若有一个奇质因子的多次幂则算多个，$2$ 的多次幂只算一个）。若它们异或和为 $0$ 则后手胜，否则先手胜。
问题是 $a_i$ 有 $10^{12}$，如何统计质因子。方法是先用 $10^4$ 内所有质数试除，能分解就分解。这样过后 $a$ 若没有分解完，则剩下的质因子都 $>10^4$，而 $a_i \le 10^12$，于是最多只剩两个质因子。此时若它是质数则只剩一个，否则就是剩两个。
指数检测用 Miller-Rabin 算法。然而网上的许多模板都无法通过这道题，包括我自己之前写的，或许是数据有意在卡？最后是这篇文章中的代码顺利通过了这题，在此感谢作者。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| const int tl = 12;
const ll p[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
ll qpow(ll x, ll y, ll mod) {
ll p = 1;
while (y) {
if (y & 1)p = (__int128)p * x % mod;
x = (__int128)x * x % mod;
y >>= 1;
}
return p;
}
bool MillerRabin(ll x) {
if (x == 1)return 0;
for (int i = 0;i < tl;i++) {
if (x == p[i])return 1;
bool ok = 0;
ll v = x - 1;
while ((v & 1) == 0)v >>= 1;
ll y = qpow(p[i], v, x);
if (y == 1)ok = 1;
else {
while (v < x - 1) {
if (y == x - 1) {
ok = 1;
break;
}
v <<= 1;
y = (__int128) y * y % x;
}
}
if (!ok)return 0;
}
return 1;
}
int n, ans = 0;
vector<int> v;
ll a;
void Solve() {
forr(i, 2, 10000) if (MillerRabin(i)) v.pb(i);
cin >> n;
rep(i, n) {
cin >> a;
int t = 0;
for(int p : v) {
if(a % p == 0) {
t++, a /= p;
while(a % p == 0) a /= p, t += (p > 2);
}
}
if(a > 1) t += 2 - MillerRabin(a);
ans ^= t;
}
if (ans) cout << "Xiaodu";
else cout << "Duduxiong";
}
|
4. 流水线搭积木
貌似是平衡树，以后有空补。