总结
今天是 noip 前的最后一次集训！哇酷哇酷！今天就主要是复习了，记录一下做的事情！好兴奋！
早上
打了昨天 T4 衍生出来的两个题目，非常好反悔贪心，是我的大脑旋转。
准备复习一下扫描线和平衡树。哦对，我要先把前天 vp 的 C 题改了。
哦对了今天发生了很有趣的事情。打乒乓球的时候乒乓球掉到池塘里面去了。里面的金鱼（也可能是鲤鱼）帮助我们把球送到了边边上让我们能够捡起乒乓球，谢谢小鱼！感谢🙇！
下午
成功通过，问题出现在一些乘法溢出了哇呜。简单说一下怎么做吧！
CF1868C
link 。
我的代码跑得很快，139ms，全开 __int128 时间都才（你猜猜我为什么要全开 __int128，因为写的时候有个地方乘法溢出了），如果再减少一下取模的数量应该可以更快。时间复杂度。
具体怎么做呢？首先对于一条链，枚举最大值，长度（点数）为，那么贡献就是。然后枚举最大值和长度。我们容易发现链的不同长度数量是的，我们要求得每种长度的链的数量，然后和上面的贡献乘起来求和就行。那么我们怎么去求数量呢？我们考虑枚举一条链，从 lca 往两个儿子两边的长度是多少，会发现对于上面几层，对应的都是满二叉树，直接计算，需要特别计算的就是二叉树最下面一层的，特殊处理一下就可以。具体实现请看代码，要预处理一下幂。
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include <bits/stdc++.h>
using namespace std;
char *p1, *p2, buf[5000000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,5000000,stdin),p1==p2)?EOF:*p1++)
#define read(x) {x=0;int ch;while(!isdigit(ch=nc()));do x=x*10+(ch^48);while(isdigit(ch=nc()));}
template<typename T>
void write(T x) {
if (x >= 10) write(x / 10);
putchar((x % 10) ^ 48);
}
int t;
using ll = long long;
ll n;
int m;
#define mod 998244353ll
ll qp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
ll gs[128];
#define N 100010
ll mi[N][128], jm[128];
signed main() {
read(t);
while (t--) {
read(n) read(m)
int cs = __lg(n), mc = cs;
if (__builtin_popcountll(n + 1) != 1) --mc;
ll ans = 0;
int mlen = cs * 2ll + 1;
if (n != 1 && !(n & (n - 1))) --mlen;
for (int j = 1; j <= mlen; ++j) {
gs[j] = 0;
for (int k = max(j - 1 - cs, 0); k * 2 <= j - 1; ++k) {
int l = j - 1 - k;
ll tmp, tt;
tt = (__int128(1) << (max(k - 1, 0) + max(l - 1, 0) + (k != l))) % mod;
if (mc < l) goto nxt;
tmp = (1ll << (mc - l + 1)) - 1;
tmp %= mod;
gs[j] += tmp * tt % mod;
nxt:
if (cs != mc) {
ll rest = n - (1ll << cs) + 1;
gs[j] += (rest / (1ll << l)) % mod * tt % mod;
rest %= (1ll << l);
ll zuo = min(rest, 1ll << max(0, l - 1));
ll you = rest - zuo;
zuo %= mod, you %= mod;
if (k < l) {
tt = zuo * ((1ll << max(k - 1, 0)) % mod) % mod + you * ((1ll << max(k - 1, 0)) % mod) % mod;
tt %= mod;
gs[j] += tt;
} else {
tt = zuo * you % mod;
gs[j] += tt;
}
}
}
gs[j] %= mod;
}
for (ll i = 1; i <= m; ++i) {
mi[i][0] = 1;
for (int j = 1; j <= mlen; ++j) {
mi[i][j] = mi[i][j - 1] * i % mod;
}
}
jm[mlen] = qp(m, (n - mlen) % (mod - 1));
for (int j = mlen - 1; j; --j) {
jm[j] = jm[j + 1] * m % mod;
}
for (ll i = 1; i <= m; ++i) {
for (int j = 1; j <= mlen; ++j) {
auto val = (mi[i][j] - mi[i - 1][j] + mod) * i % mod * jm[j] % mod;
ans += gs[j] * val % mod;
}
}
ans %= mod;
write(ans);
putchar('\n');
}
return 0;
}
|
没有打扫描线和平衡树。随缘吧，加油！
后记
再次感谢小鱼！祝你们好运，也祝我们好运，rp++！
