ICPC 2024 杭州站 打星游记
其他两位队员都懒得写，那就我来写吧。
Day ??
正在信友队训练。被告知说信友队赞助了杭州站，送了几个名额，我们可能可以打星参赛。
感觉挺新奇的，有些兴奋，毕竟以前从未参加过 XCPC 呢。
Day ?
正式的通知下来了，信友队有四支队，名字是祖传的 学军信友队 [1-4] 队。
剩下三支队名额刚好分给我们机房一共九个人。
我在 $2$ 队，队友分别是 APIO Ag 爷 [dspt](https://www.luogu.com.cn/user/282929) 和 NOI Ag 爷 [szh](https://www.luogu.com.cn/user/290784)，瑟瑟发抖，可以想象到被带飞的场景。估计只能端茶倒水了。
$3$ 队是传奇丁真王 [xhgua](https://www.luogu.com.cn/user/410239) 和机房唯二勾八 [lsj2009](https://www.luogu.com.cn/user/468657) 和 jiangly 粉丝 [Misty7](https://www.luogu.com.cn/user/344543)。
$4$ 队是机房小南梁 [yshpdyt](https://www.luogu.com.cn/user/229008) 和机房奶龙 [lycc](https://www.luogu.com.cn/user/486675) 和山东pc王 [王哥](https://www.luogu.com.cn/user/374987)。
在正赛前 $3,4$ 队都进行了一至若干场的 XCPC 场次的模拟训练，并且都发挥出了不错的实力。
但我们队从未进行过任何一场训练，一直都是自己管自己写自己的题，摆到正赛前。
我一直打算开场就默写码头，但有人说我码头写完比赛就结束了。
## Day 0
11 月 9 日。
发现身份证落在家里了，急急急。
我们计划下午去打个热身赛就润，但上午甚至还有模拟赛。
于是模拟赛就咕掉了。
准备中午的时候三支队集合后一起坐地铁去杭师大，但是传奇 yshpdyt 一觉睡到了中午，差点迟到。
到杭师大就急急急找到位置坐下了。
第一次打 XCPC，就连热身看起来都十分新奇。
从未见过一个挂着气球有大屏幕的考场。
然后热身赛开始了。大屏幕上出现了 Judge Queue，很神奇，很好玩。
发现是全英文题面，寄。
> 注：热身赛我们并没有带字典。因为 dspt 曾经在初中里获得了 spelling bee（拼词大赛）的冠军，获得了 walking dictionary 的头衔。因此，他认为如果热身赛的题目他看得懂，那么甚至正赛也无需携带字典，他会翻译所有题目。
一共是四道题，我们队当时并没有什么策略，但由于我写题需要码头，因此由我先上机默写我的码头。
结果码头还没写完 dspt 就已经会了 A，换人，过题。
这时我下来看 C，发现这个题似曾相识，于是和 szh 讨论，于是他会了，换人。
szh 写完交了一发，没过，很神秘。
此时广播里在播报内容，但是很糊，还是全英文，难度严格大于英语听力。
幸好 dspt 擅长英语，翻译说题目顺序有问题，于是交到了正确的题目上，过题。
此时我开了 B，有一些初步的想法，和 dspt 和 szh 讨论，szh 又会了，遂写之，没过。
他发现有 corner case 没判，写之，没过。
此时我和 dspt 在看 D，但是我没看懂题目，幸亏 dspt 的翻译。
发现只要用字典树随便做一下就好了，又听 dspt 听广播说精度 checker 好像挂了，因此换我写 D，没过。
此时 B 重测完了，还是没过。
开始瞪眼，szh 发现他 B 做法假的妈妈都不认识了，稍微一改，过了。
szh 又发现我的 D 没有判前缀，改改改，过了。
罚时上天，严格低于 $3$ 队，感觉输完了。
之后开始在赛场上随机游走，随机面基了一些人，包括但不限于 [\_jimmywang\_](https://www.luogu.com.cn/user/90706) 和 [SalomeJLQ](https://www.luogu.com.cn/user/246979)，都是高二考上西湖大学。
还获得了 Hydro 挂件，好看捏。
之后尝试在杭师大游走找地方吃饭，失败了。
碰到了随机刷新的 [猫猬兽](https://www.luogu.com.cn/user/87318)。
晚上就回信友队了。
感谢我的家长把我的身份证送来了。
十一点多就睡了。
## Day 1
早上七点被闹醒，根本起不来啊。
赶到了信友队集合出发，有的人还是不出意外地迟到了。
马不停蹄地赶去了杭师大，找到位置后安稳坐下。
发现座位上有吧唧和明信片，好看捏，喜欢。
坐下后困意席卷而来，但是就要开赛了，只敢趴一会。
在赛前做了一些准备工作，我和 szh 互相确认了电子产品没有带入考场，拿了身份证。
**之后** dspt 从家里过来了，他拿了一本字典，我笑了。
开赛前 dspt 意识到没有拿身份证进考场，于是去包里拿了。
为了区分矿泉水瓶，dspt 把标签纸撕下来了之后上下倒过来贴，我把标签纸撕下来了之后正反反过来贴。
开赛前，我们一致了我们的目标，尝试拿金牌。
---
下发了试卷袋，很新奇啊，第一次看到 OI 比赛使用试卷袋装的！
九点，开赛了，我把试卷袋优雅地拆开，取出试题。
想先去默写码头，发现机子还不能操作，于是只能读题了。
不知道先读什么，于是翻阅试卷，看到了 M，发现应该是一个不难的题。
还没读完就说机子可以用了，遂上机，先默个码头。
默完了，此时 dspt 已经会 A 了，遂写之，过题，激励了我们的士气。
szh 会了 K 之后貌似一直在看 C，当他说他会了的时候我两眼震惊。
我下机后就一直在想 M，感觉应该是一个可做题。
dspt 下机后 szh 开始写 K，遂取之。
因为机位空着，szh 开始写 C，我将我的 M 讲给 dspt，dspt 一会后就有了一个大约 $O(n\sqrt V)$ 的做法，但是是过不了的。
dspt 继续思考 M，而我取去跟榜，发现目前可做题有 E，H 等，遂读题，开始想 E，想到一个做法，结果假的妈妈都不认识了，又想了一个做法，觉得全都是道理。
突然有人叫住了 dspt：“手环给我。”原来是 dspt 忘记把运动手环放在场外了，心里一紧，这下要 dq 了。
幸好貌似并无大碍，继续做题。
dspt 发现貌似可以原地变成 $O(\sqrt V+n\tau(V))$，于是勒令 szh 下机，dspt 开写 M。
我们一直认为计算几何应当最后写，因此我喂给 szh 了 E 的题意。他思索一下发现没什么头绪，我喂给了他我的做法，他觉得假的妈妈都不认识了，反手就把我叉了。
于是继续想，szh 发现我的做法只要稍微改一改就全都是道理，我觉得很有道理。
此时 dspt 写完了 M，还在调，我喂给了 szh H 的题意。
dspt 调完了，很担心自己的常数，交，喜提一发罚时，竟然是 T。
dspt 把 map 改成了 unordered_map，交，又是 T。
dspt 又改了一改，还是 T。
dspt 觉得很神秘，快速写了个拍以后下了机，换我写 E，他和 szh 讨论 H。
我码码码，写完之后挂的妈妈都不认识了，发现我排序了个寂寞，改改改，改了一会过样例了，交，**过了**。
此时 szh 已经会了 H，还会了之前开的 F，上机写代码，屏幕分成两半，左边 dspt 使用瞪眼法调题。
dspt 还开了 G，和 szh 讨论了一下感觉应该是一个很码量的题，遂弃。
我选择跟榜开题，选择了 B，发现是一个 ds，读完题瞬间会了双 $\log$ 做法。
$n$ 是 $1e6$，经验丰富的 dspt 告诉我 $1e6$ 过双 $\log$ 做梦去吧。
也对，如果双 $\log$ 能过，现在怎么会只过了这么点。
开始精心思考怎么优化。此时 dspt 突然红温，发现他所谓的常数问题竟然是，多册没清空！
清之，过了。
szh 继续写，写完了，交，过了，开始写 F。
dspt 开了 L，有一些神秘的想法，但是并没有进一步的成果。
我和他讲了 B，他觉得这道题看起来就很可做。
过了一会，dspt 想到了 B 的单 $\log$ 做法，很厉害！
此时 dspt 问 szh 有没有理解错 F 的题意，于是 szh 成功发现了自己没有理解到强制在线，做法错的妈妈都不认识了。换人，dspt 开写 B。
szh 继续想 F 怎么强制在线，我跟榜，发现 I,J,L 都是当前的热门题，不会交互，不会像 L 这样的牛逼题。J 看起来是一个很神秘的状压计数，遂读题。
dspt 码码码，szh 还在想，我读了两遍 J 却读不懂题意，再读。
szh 会了 F 的强制在线，竟然直接从离线的根号变成了单 $\log$，太强大了。
我读了 $\inf$ 遍 J，终于读懂了是要可重集计数，就是说出题人能不能下次给一个形式化题意呢。
把题意喂给了 szh，szh 有所想法，想了一会，发现只要枚举 $\mathbb C$ 在 $\mathbb M$ 上高维前缀和搞一搞就可以了！太强了！
dspt 过样例了，交一发，没过。
此时还有一个半小时，就快要封榜了，而我们还在银牌区，只有 $5$ 题，距离金牌还有点远。
我们加油打气不要急，我们手上藏了题！
意识到可以打印代码后打印了 B 的代码，打印了 B 的代码，迅速换 szh 写 F。
我和 dspt 一起丁真他的 B，他发现，他传奇般没有 push_down！
改之，直接过了。
szh 还在码码码，我和 dspt 开了 I，想了一会感觉没什么头绪，只知道要二分，但不知道怎么二分。
此时封榜了，心里有点紧张，现在的一切都是未知。
szh 写完了，交了一发，没过。
他迅速意识到有 corner case 没判，改改改，没过。
我和 dspt 看他的代码，为啥 tarjan 里有并查集啊？这确定对吗？
他说，无向图的时候确实是对的。
真厉害啊。
换我上机，帮他写了一个正常的 tarjan，他改了改码风后直接过了。
听到了吗，NOI Ag 不会写 tarjan。
此时还有半个小时。
我们现在 $7$ 题了，根据分榜前的排名是金牌，但是封榜后就不好说了，很多 $6$ 题队都在厚积薄发，而我们拥有者超级罚时。
szh 开始写 J，他觉得估计会寄，我们鼓励他，写得完最好，写不完问题也不大。
我和 dspt 看 I，还是没什么头绪。
szh 码码码，在 $288$ 分钟的时候写完了，样例一发过。
提交，直接过了！
$8$ 题了，我看了看榜，稳金啊！
最后十几分钟，szh 懒得写他的 C 了。没人动电脑，我们稍微聊了一会天，总结了一下今天的表现。
战神（szh，最后关头过 J 一战封神）+ 战犯（dspt，M 三发 B 一发）+ 逃犯（我，contribution=1）= Au
---
出场后碰到了一些已经毕业的学长，稍微聊了聊。
$1$ 队差点就阿克了，$3$ 队和 $4$ 队貌似都坠机了。
火之剑圣下西洋、轰炸机数学学院、hzjsxxy、国际信息学奥赛金牌教练、NOI 钻石教师、杭州学军中学正高级教师、杭州学军中学拔尖创新中心主任、信友队科技培训有限公司创始人、学军中学信友队 $1$ 队 coach、学军中学信友队 $2$ 队 coach、学军中学信友队 $3$ 队 coach、学军中学信友队 $4$ 队 coach、徐先友老师为我们队在赛场门口进行了合影。
意识到可以把印有队名的挡板带走时，遂回赛场取之。
结果 $3$ 队 $4$ 队和 dspt 都回去了，只剩下我和 szh 去听讲评。
发现 I 也不是很困难，但确实时间很珍贵，交互做不来。
之后看了滚榜，还是比较刺激的。
最终获得了总榜 $\text{rk}25$，打星榜 $\text{rk}10$，初高中打星榜 $\text{rk}7$。
只有前五有实体牌，还是太菜了啊。
结束后，szh 就回家了，准备出发去 bnds 参加 CTT 集训了。
dspt 回家了。
我在和 \_jimmywang\_ 等面基，吃了晚饭后就回信友队了。
---
附：我的考场版码头（2024 年版）
```cpp
#include <bits/stdc++.h>
#define fq(i,a,b) for (int i = (a); i <= (b); i++)
#define fnq(i,a,b) for (int i = (a); i < (b); i++)
#define nfq(i,a,b) for (int i = (a); i >= (b); i--)
#define nfnq(i,a,b) for (int i = (a); i > (b); i--)
using namespace std;
#define int ll
typedef long long ll;
inline int rd () {
int f = 1;
char ch = getchar ();
while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
int num = 0;
while (isdigit (ch)) num = num * 10 + ch - '0', ch = getchar ();
return num * f;
}
#define d rd ()
signed main () {
return 0;
}
```
附：我的平时版码头（2024.11.6 版）
```cpp
// last update: 2024/11/06
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define fq(i,a,b) for (int i = (a); i <= (b); i++)
#define fnq(i,a,b) for (int i = (a); i < (b); i++)
#define nfq(i,a,b) for (int i = (a); i >= (b); i--)
#define nfnq(i,a,b) for (int i = (a); i > (b); i--)
#define fqs(i,a,b,c) for (int i = (a); i <= (b); i += (c))
#define fnqs(i,a,b,c) for (int i = (a); i < (b); i += (c))
#define nfqs(i,a,b,c) for (int i = (a); i >= (b); i -= (c))
#define nfnqs(i,a,b,c) for (int i = (a); i > (b); i -= (c))
#define elif else if
#define McasesT int T = d; while (T--)
#define Mcases(T) int T = d; while (T--)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define all(v) v.begin (), v.end ()
#define vi vector <int>
#define vpii vector <pii>
using namespace std;
#define int ll
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef signed i32;
typedef double db;
typedef long double ld;
//#define FileIO
#if defined(FileIO)
const string FileIOName = "1";
int FILEIO (string IN, string OUT) {
try {
freopen ((FileIOName + IN).c_str (), "r", stdin);
freopen ((FileIOName + OUT).c_str (), "w", stdout);
return 0;
} catch (int) {
return -1;
}
}
int freFILEIO = FILEIO (".in", ".out");
#endif
inline int rd () {
int f = 1;
char ch = getchar ();
while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
int num = 0;
while (isdigit (ch)) num = num * 10 + ch - '0', ch = getchar ();
return num * f;
}
#define d rd ()
inline int rd (const int modp) {
int f = 1;
char ch = getchar ();
while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
int num = 0;
while (isdigit (ch)) num = (num * 10 + ch - '0') % modp, ch = getchar ();
return (num * f % modp + modp) % modp;
}
namespace lay {
struct Edge {
int v, nxt;
Edge () {}
Edge (int _v, int _nxt) {v = _v, nxt = _nxt;}
};
template <int VERTEXES, int EDGES, int initecnt = 0>
struct Graph {
Edge edge[EDGES];
int head[VERTEXES], ecnt;
void addedge (int u, int v) {edge[++ecnt] = Edge (v, head[u]); head[u] = ecnt;}
void addEdge (int u, int v) {addedge (u, v), addedge (v, u);}
void init () {memset (head, 0, sizeof head); ecnt = initecnt;}
Graph () {init ();}
};
template <typename WT>
struct EdgeW {
int v, nxt; WT w;
EdgeW () {}
EdgeW (int _v, WT _w, int _nxt) {v = _v, w = _w, nxt = _nxt;}
};
template <int VERTEXES, int EDGES, typename WT = int, int initecnt = 0>
struct GraphW {
EdgeW <WT> edge[EDGES];
int head[VERTEXES], ecnt;
void addedge (int u, int v, WT w) {edge[++ecnt] = EdgeW <WT> (v, w, head[u]); head[u] = ecnt;}
void addEdge (int u, int v, WT w) {addedge (u, v, w), addedge (v, u, w);}
void init () {memset (head, 0, sizeof head); ecnt = initecnt;}
GraphW () {init ();}
};
template <int VERTEXES, int EDGES, typename WT = int>
struct GraphFW : public GraphW <VERTEXES, EDGES, WT, 1> {
void addEdge (int u, int v, WT w) {this -> addedge (u, v, w), this -> addedge (v, u, 0);}
};
template <typename WT1, typename WT2>
struct EdgeWC {
int v, nxt; WT1 w; WT2 c;
EdgeWC () {}
EdgeWC (int _v, WT1 _w, WT2 _c, int _nxt) {v = _v, w = _w, c = _c, nxt = _nxt;}
};
template <int VERTEXES, int EDGES, typename WT1 = int, typename WT2 = int, int initecnt = 0>
struct GraphWC {
EdgeWC <WT1, WT2> edge[EDGES];
int head[VERTEXES], ecnt;
void addedge (int u, int v, WT1 w, WT2 c) {edge[++ecnt] = EdgeWC <WT1, WT2> (v, w, c, head[u]); head[u] = ecnt;}
void addEdge (int u, int v, WT1 w, WT2 c) {addedge (u, v, w, c), addedge (v, u, w, c);}
void init () {memset (head, 0, sizeof head); ecnt = initecnt;}
GraphWC () {init ();}
};
template <int VERTEXES, int EDGES, typename WT1 = int, typename WT2 = int>
struct GraphFWC : public GraphWC <VERTEXES, EDGES, WT1, WT2, 1> {
void addEdge (int u, int v, WT1 w, WT2 c) {this -> addedge (u, v, w, c), this -> addedge (v, u, 0, -c);}
};
#define fe(G,u) for (int i = G.head[u], v; v = G.edge[i].v, i; i = G.edge[i].nxt)
#define feh(G,u,h) for (int i = h[u], v; v = G.edge[i].v, i; i = G.edge[i].nxt)
#define few(G,u) for (auto [i, v, w] = make_tuple (G.head[u], int(), int()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
#define fewt(G,u,T) for (auto [i, v, w] = make_tuple (G.head[u], int(), T()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
#define fewh(G,u,h) for (auto [i, v, w] = make_tuple (h[u], int(), int()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
#define fewht(G,u,h,T) for (auto [i, v, w] = make_tuple (h[u], int(), T()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
#define fewc(G,u) for (auto [i, v, w, c] = make_tuple (G.head[u], int(), int(), int()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
#define fewct(G,u,T1,T2) for (auto [i, v, w, c] = make_tuple (G.head[u], int(), T1(), T2()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
#define fewch(G,u,h) for (auto [i, v, w, c] = make_tuple (h[u], int(), int(), int()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
#define fewcht(G,u,h,T1,T2) for (auto [i, v, w, c] = make_tuple (h[u], int(), T1(), T2()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
}
namespace lay {
class cpx {
public:
double a, b;
cpx () {a = 0, b = 0;}
cpx (double _a) {a = _a, b = 0;}
cpx (double _a, double _b) {a = _a, b = _b;}
friend cpx operator + (cpx a, cpx b) {return cpx (a.a + b.a, a.b + b.b);}
friend cpx operator - (cpx a, cpx b) {return cpx (a.a - b.a, a.b - b.b);}
friend cpx operator * (cpx a, cpx b) {return cpx (a.a * b.a - a.b * b.b, a.b * b.a + a.a * b.b);}
friend cpx operator / (cpx a, cpx b) {return cpx ((a.a * b.a + a.b * b.b) / (b.b * b.b + b.a * b.a), (a.b * b.a - a.a * b.b) / (b.b * b.b + b.a * b.a));}
friend cpx& operator += (cpx &a, cpx b) {return a = a + b;}
friend cpx& operator -= (cpx &a, cpx b) {return a = a - b;}
friend cpx& operator *= (cpx &a, cpx b) {return a = a * b;}
friend cpx& operator /= (cpx &a, cpx b) {return a = a / b;}
};
}
template <typename T>
inline void Write (T x) {
if (x < 0) putchar ('-'), x *= -1;
if (x >= 10) Write (x / 10);
putchar (x % 10 + '0');
}
template <typename T> void write (char sep, char end, T x) {Write (x); putchar (end);}
template <typename T, typename... Ts> void write (char sep, char end, T x, Ts... xs) {Write (x); putchar (sep); write (sep, end, xs...);}
template <typename... Ts> void output (Ts... xs) {write (' ', '\n', xs...);}
namespace lay {
template <typename T = int>
class _Math {
public:
static T exmax (T x) {return x;}
template <typename... Ts> static T exmax (T x, Ts... xs) {return max (x, exmax (xs...));}
static T exmin (T x) {return x;}
template <typename... Ts> static T exmin (T x, Ts... xs) {return min (x, exmin (xs...));}
template <typename... Ts> static T exgmax (T &x, Ts... xs) {return x = exmax (x, xs...);}
template <typename... Ts> static T exgmin (T &x, Ts... xs) {return x = exmin (x, xs...);}
static T gcd (T a, T b) {return !b ? a : gcd (b, a % b);}
static T lcm (T a, T b) {return a / gcd (a, b) * b;}
static T exgcd (T a, T b, T& x, T& y) {
if (!b) {x = 1; y = 0; return a;}
T ans = exgcd (b, a % b, y, x);
y -= a / b * x;
return ans;
}
static T crt (size_t n, T *a, T *p) {
T M = 1, ans = 0;
fq (i, 1, n) M *= p[i];
fq (i, 1, n) {
T m = M / p[i];
T x, y;
exgcd (m, p[i], x, y);
ans += (x < 0 ? x + p[i] : x) * a[i] * m;
} return ans % M;
}
static T excrt (size_t n, T *a, T *b) {
T M = b[1], ans = a[1];
fq (i, 2, n) {
T aa = M, c = (a[i] - ans % b[i] + b[i]) % b[i];
T x, y;
T gcd = exgcd (aa, b[i], x, y);
if (c % gcd) return -1;
T bg = b[i] / gcd;
x = c / gcd * x % bg;
ans += x * M;
M *= bg;
ans = (ans % M + M) % M;
}
return (ans % M + M) % M;
}
static T power (T a, T b, T p) {
T c = 1;
while (b) {
if (b & 1) c = c * a % p;
a = a * a % p;
b >>= 1;
} return c;
}
private:
static T C (T n, T m, T p) {
T ans = 1;
fq (i, n - m + 1, n) ans = ans * i % p;
fq (i, 2, m) ans = ans * power (i, p - 2, p) % p;
return ans;
}
public:
static T lucas (T n, T m, T p) {
if (!m || !n) return 1;
return lucas (n / p, m / p, p) * C (n % p, m % p, p) % p;
}
static T bsgs (T a, T b, T p) {
T mul = 1, t = sqrt (p) + 1;
static map <T, T> mp;
mp.clear ();
fq (i, 1, t) {
mul = mul * a % p;
mp[b * mul % p] = i;
}
T mull = mul;
fq (i, 1, t) {
if (mp[mull]) return i * t - mp[mull];
mull = mull * mul % p;
} return -1;
}
};
const _Math <> iMath;
auto Math = iMath;
}
namespace lay {
template <typename T = int>
class _ExMath {
private:
static void expr_skpop (stack <char> &sk1, stack <T> &sk2, T fun (T, T, char)) {
T r = sk2.top (); sk2.pop ();
T l = sk2.top (); sk2.pop ();
char op = sk1.top (); sk1.pop ();
sk2.push (fun (l, r, op));
}
public:
static T expr (string s, map <char, short> mp, T fun (T, T, char)) {
static stack <char> sk1;
static stack <T> sk2;
while (!sk1.empty ()) sk1.pop ();
while (!sk2.empty ()) sk2.pop ();
s = '(' + s + ')';
int len = s.size ();
fnq (i, 0, len) {
if (isdigit (s[i])) {
T num = 0;
while (isdigit (s[i])) num = num * 10 + s[i] - '0', ++i;
--i;
sk2.push (num);
} elif (s[i] == '(') {
sk1.push ('(');
} elif (s[i] == ')') {
while (sk1.top () != '(')
expr_skpop (sk1, sk2, fun);
sk1.pop ();
} else {
while (!sk1.empty () && sk1.top () != '(' && mp[sk1.top ()] >= mp[s[i]])
expr_skpop (sk1, sk2, fun);
sk1.push (s[i]);
}
}
return sk2.top ();
}
};
const _ExMath <> iExMath;
auto ExMath = iExMath;
}
namespace lay {
constexpr int Eular (int x) {
int sqrtx = sqrt (x);
int ans = x;
fq (i, 2, sqrtx) if (x % i == 0) {
ans = ans / i * (i - 1);
while (x % i == 0) x /= i;
} if (x > 1) ans = ans / x * (x - 1);
return ans;
}
template <int p>
class Modint {
private:
const static int eular = Eular (p);
int num;
static int unsafe_constructor (int x) {return (x % p + p) % p;}
public:
int toInt () {return num;}
Modint () {}
Modint (int x) {num = unsafe_constructor (x);}
friend Modint operator + (Modint a, Modint b) {int c = a.num + b.num; if (c >= p) c -= p; return Modint (c);}
friend Modint operator - (Modint a, Modint b) {int c = a.num - b.num; if (c < 0) c += p; return Modint (c);}
friend Modint operator * (Modint a, Modint b) {return Modint <p> :: unsafe_constructor (a.num * b.num);}
friend Modint operator / (Modint a, Modint b) {return Modint <p> :: unsafe_constructor (a.num * Math.power (b.num, p - 2, p));}
friend Modint operator ^ (Modint a, Modint b) {return Math.power (a.num, b.num % Modint <p> :: eular, p);}
friend Modint& operator += (Modint &a, Modint b) {return a = a + b;}
friend Modint& operator -= (Modint &a, Modint b) {return a = a - b;}
friend Modint& operator *= (Modint &a, Modint b) {return a = a * b;}
friend Modint& operator /= (Modint &a, Modint b) {return a = a / b;}
friend Modint& operator ^= (Modint &a, Modint b) {return a = a ^ b;}
Modint& operator ++ () {*this += 1; return *this;}
Modint operator ++ (signed) {Modint cpy = *this; ++(*this); return cpy;}
Modint& operator -- () {*this -= 1; return *this;}
Modint operator -- (signed) {Modint cpy = *this; --(*this); return cpy;}
friend istream& operator >> (istream& in, Modint x) {x = rd (p); return in;}
friend ostream& operator << (ostream&out, Modint x) {out << x.toInt (); return out;}
};
}
namespace lay {
inline int lowbit (int i) {return i & -i;}
template <int SZ>
class BIT {
int c[SZ];
int n;
public:
BIT () {}
void set (int x) {n = x;}
void clear () {fq (i, 0, n) c[i] = 0;}
BIT (int x) {set (x);}
void add (int i, int x) {while (i <= n) c[i] += x, i += lowbit (i);}
int ask (int i) {int s = 0; while (i) s += c[i], i -= lowbit (i); return s;}
int query (int l, int r) {return ask (r) - ask (l - 1);}
};
}
namespace lay {
template <int p>
struct _Cipolla {
int i;
struct comp {
int a, b;
};
comp mul (comp a, comp b) {
return {(a.a * b.a + a.b * b.b % p * i) % p, (a.b * b.a + a.a * b.b) % p};
}
int power (comp a, int b) {
comp c = {1, 0};
while (b) {
if (b & 1) c = mul (c, a);
a = mul (a, a);
b >>= 1;
} return c.a;
}
pair <int, int> solve (int n) {
if (n == 0) return {0, -1};
if (Math.power (n, (p - 1) >> 1, p) == p - 1) return {-1, -1};
mt19937 rnd(random_device {} ());
int c = -1;
while (1) {
c = rnd () % (p - 1) + 1; i = (c * c - n + p) % p;
if (power ({i, 0}, (p - 1) >> 1) == p - 1) break;
} int s = power ({c, 1}, (p + 1) >> 1); return {s, p - s};
}
pair <int, int> operator () (int n) {
return solve (n);
}
};
namespace poly {
const int p = 998244353;
const int g = 3, gi = Math.power (g, p - 2, p);
const int I = Math.power (g, (p - 1) >> 2, p);
struct _NTT {
private:
vi Turn;
vi gs, gis;
public:
int size () {return Turn.size ();}
void init (int len) {
int n = 1; while (n < len) n <<= 1;
Turn.resize (n);
Turn[0] = 0;
fnq (i, 1, n) Turn[i] = (Turn[i >> 1] | (i & 1 ? n : 1)) >> 1;
}
void ntt (vi &x, bool op) {
int n = size ();
if ((int)x.size () < n) x.resize (n);
fnq (i, 0, n) if (i < Turn[i]) swap (x[i], x[Turn[i]]);
int cc = 1;
for (int h = 2; h <= n; h <<= 1, ++cc) {
int Wn = (op ? gis[cc] : gs[cc]);
for (int i = 0; i < n; i += h) {
int w = 1;
fnq (j, 0, h >> 1) {
int a = x[i + j], b = 1ll * x[i + j + (h >> 1)] * w % p;
x[i + j] = (a + b) % p;
x[i + j + (h >> 1)] = (a - b + p) % p;
w = 1ll * w * Wn % p;
}
}
}
if (op) {
int inv = Math.power (n, p - 2, p);
fnq (i, 0, n) x[i] = 1ll * x[i] * inv % p;
}
}
_NTT () {
gs.resize (25);
fq (i, 1, 23) gs[i] = Math.power (g, (p-1) >> i, p);
gis.resize (25);
fq (i, 1, 23) gis[i]= Math.power(gi, (p-1) >> i, p);
}
} NTT;
vi poly_mul (vi a, vi b) {
NTT.init (a.size () + b.size () - 1);
NTT.ntt (a, 0);
NTT.ntt (b, 0);
fnq (i, 0, NTT.size ()) a[i] = 1ll * a[i] * b[i] % p;
NTT.ntt (a, 1);
return a;
}
vi poly_inv (vi a, int n) {
if ((int)a.size () > n) a.resize (n);
if (n == 1) return {Math.power (a[0], p - 2, p)};
auto b = poly_inv (a, (n + 1) >> 1);
auto c = poly_mul (a, b);
fnq (i, 0, (int)c.size ()) c[i] = (p - c[i]) % p;
c[0] = (c[0] + 2) % p;
c = poly_mul (c, b);
c.resize (n);
return c;
}
vi poly_int (vi a, int c = 0) {
vi b;
b.pb (c);
fnq (i, 0, (int)a.size ())
b.pb (1ll * Math.power (i+1, p-2, p) * a[i] % p);
return b;
}
vi poly_diff (vi a) {
vi b;
fnq (i, 1, (int)a.size ())
b.pb (1ll * i * a[i] % p);
return b;
}
vi poly_ln (vi a, int n) {
if ((int)a.size () > n) a.resize (n);
auto b = poly_diff (a);
auto c = poly_mul (b, poly_inv (a, n));
c.resize (n + 1);
auto e = poly_int (c, 0);
return e;
}
vi poly_add (vi a, vi b) {
vi c;
c.resize (max (a.size (), b.size ()));
fnq (i, 0, (int)c.size ()) c[i] = 0;
fnq (i, 0, (int)a.size ()) c[i] = a[i];
fnq (i, 0, (int)b.size ()) c[i] = (c[i] + b[i]) % p;
return c;
}
vi poly_sub (vi a, vi b) {
vi c;
c.resize (max (a.size (), b.size ()));
fnq (i, 0, (int)c.size ()) c[i] = 0;
fnq (i, 0, (int)a.size ()) c[i] = a[i];
fnq (i, 0, (int)b.size ()) c[i] = (c[i] + p - b[i]) % p;
return c;
}
vi poly_exp (vi a, int n) {
if ((int)a.size () > n) a.resize (n);
if (n == 1) return {1};
auto b = poly_exp (a, (n + 1) >> 1);
auto e = poly_ln (b, n);
auto f = poly_sub (a, e);
f[0] = (f[0] + 1) % p;
auto g = poly_mul (b, f);
g.resize (n);
return g;
}
vi poly_mul (vi a, int b) {
vi c;
for (auto x : a) c.pb (1ll * x * b % p);
return c;
}
vi poly_sin (vi a, int n) {
auto b = poly_mul (a, I);
auto be = poly_exp (b, n);
auto c = poly_mul (a, (p-I) % p);
auto ce = poly_exp (c, n);
auto e = poly_sub (be, ce);
auto f = poly_mul (e, Math.power (2 * I % p, p-2, p));
if ((int)f.size () > n) f.resize (n);
return f;
}
vi poly_cos (vi a, int n) {
auto b = poly_mul (a, I);
auto be = poly_exp (b, n);
auto c = poly_mul (a, (p-I) % p);
auto ce = poly_exp (c, n);
auto e = poly_add (be, ce);
auto f = poly_mul (e, Math.power (2, p-2, p));
if ((int)f.size () > n) f.resize (n);
return f;
}
vi poly_R (vi a, int n) {
a.resize (n+1);
fnq (i, 0, (n+1) >> 1) swap (a[i], a[n-i]);
return a;
}
void poly_print(vi a, int n) {
int lim = min ((int)a.size()-1, n);
fq (i, 0, lim) cout << a[i] << " ";
fq (i, lim+1, n) cout << "0 ";
puts ("");
}
void poly_print(vi a) {
int n = a.size () - 1;
while (n && a[n] == 0) --n;
poly_print (a, n);
}
void poly_seize (vi &a) {
int n = a.size () - 1;
while (n && a[n] == 0) --n;
a.resize (n+1);
}
pair <vi, vi> poly_div (vi a, vi b) {
poly_seize (a); poly_seize (b);
int n = a.size()-1, m = b.size()-1;
if (n < m) return {{0}, a};
auto ar = poly_R (a, n);
auto br = poly_R (b, m);
auto qr = poly_mul (ar, poly_inv (br, n-m+1));
auto q = poly_R (qr, n-m);
auto r = poly_sub (a, poly_mul (b, q));
q.resize (n-m+1); r.resize (m);
return {q, r};
}
void poly_multi_eval_solve1 (vi &ps, int l, int r, int rt, vector <vi > &h) {
if (l == r) {
h[rt] = {(p - ps[l]) % p, 1};
return;
}
int mid = (l + r) >> 1;
poly_multi_eval_solve1 (ps, l, mid, rt << 1, h);
poly_multi_eval_solve1 (ps, mid + 1, r, rt << 1 | 1, h);
h[rt] = poly_mul (h[rt << 1], h[rt << 1 | 1]);
poly_seize (h[rt]);
}
void poly_multi_eval_solve2 (vi f, vi &ps, int l, int r, int rt, vector <vi > &h, vi &g) {
f = poly_div (f, h[rt]).se;
// if (l == r) {
// g[l] = f[0];
// return;
// }
if (r - l + 1 <= 1024) {
int n = f.size () - 1;
fq (i, l, r) {
int s = 0, x = ps[i];
nfq (j, n, 0) s = (1ll * s * x + f[j]) % p;
g[i] = s;
}
return;
}
int mid = (l + r) >> 1;
poly_multi_eval_solve2 (f, ps, l, mid, rt << 1, h, g);
poly_multi_eval_solve2 (f, ps, mid + 1, r, rt << 1 | 1, h, g);
}
vi poly_multi_eval (vi &f, vi &ps) {
int n = ps.size ();
vector <vi> h; h.resize (n << 2);
poly_multi_eval_solve1 (ps, 0, n-1, 1, h);
vi g; g.resize (n);
poly_multi_eval_solve2 (f, ps, 0, n-1, 1, h, g);
return g;
}
void poly_fast_inter_solve1 (vector <pii> &ps, int l, int r, int rt, vector <vi > &h) {
if (l == r) {
h[rt] = {(p - ps[l].fi) % p, 1};
return;
}
int mid = (l + r) >> 1;
poly_fast_inter_solve1 (ps, l, mid, rt << 1, h);
poly_fast_inter_solve1 (ps, mid + 1, r, rt << 1 | 1, h);
h[rt] = poly_mul (h[rt << 1], h[rt << 1 | 1]);
poly_seize (h[rt]);
}
vi poly_fast_inter_solve2 (vector <pii> &ps, vi &gx, int l, int r, int rt, vector <vi > &h) {
if (l == r)
return {1ll * ps[l].se * Math.power (gx[l], p-2, p) % p};
int mid = (l + r) >> 1;
auto vl = poly_mul (h[rt << 1 | 1], poly_fast_inter_solve2 (ps, gx, l, mid, rt << 1, h));
auto vr = poly_mul (h[rt << 1], poly_fast_inter_solve2 (ps, gx, mid + 1, r, rt << 1 | 1, h));
auto v = poly_add (vl, vr);
poly_seize (v);
return v;
}
vi poly_fast_inter (vector <pii> &ps) {
int n = ps.size ();
vector <vi> h; h.resize (n << 2);
poly_fast_inter_solve1 (ps, 0, n-1, 1, h);
auto gg = poly_diff (h[1]);
vi xs; xs.resize (n);
fnq (i, 0, n) xs[i] = ps[i].fi;
auto gx = poly_multi_eval (gg, xs);
auto f = poly_fast_inter_solve2 (ps, gx, 0, n-1, 1, h);
return f;
}
// for a_0=1
vi poly_power (vi a, int k, int n) {
auto b = poly_ln (a, n);
auto c = poly_mul (b, {k});
auto e = poly_exp (c, n);
return e;
}
// for all but a_0==0 and k is large and k%p is small
vi poly_power (vi a, int n, int k1, int k2) {
int len = min ((int)a.size (), n);
int t = 0; while (t < len && a[t] == 0) ++t;
if (t == len || t * k1 >= n) return vi (n, 0);
int x = a[t], invx = Math.power (x, p-2, p);
vi aa;
fq (i, t, len - 1) aa.pb (a[i] * invx % p);
int nn = n - t;
auto b = poly_ln (aa, nn);
auto c = poly_mul (b, {k1});
auto e = poly_exp (c, nn);
auto ee = poly_mul (e, {Math.power (x, k2, p)});
vi f (t * k1, 0);
int lim = n - t * k1;
fnq (i, 0, lim) f.pb (ee[i]);
return f;
}
pair <vi, vi> poly_sqrt (vi a, int n) {
static _Cipolla <p> Cipolla;
auto sqs = Cipolla (a[0]);
int sq1 = sqs.fi, sq2 = sqs.se;
if (sq1 == -1) return {{}, {}};
const int inv2 = Math.power (2, p-2, p);
auto b = poly_mul (a, {Math.power (a[0], p-2, p)});
auto c = poly_ln (b, n);
auto e = poly_mul (c, {inv2});
auto f = poly_exp (e, n);
auto g1 = poly_mul (f, {sq1});
vi g2 = {};
if (sq2 != -1) g2 = poly_mul (f, {sq2});
return {g1, g2};
}
}
}
// #define COUNTING_PROBLEM
#if defined (COUNTING_PROBLEM)
#define padd(x,y) (x = (x + y) % p)
#endif
void gmax (int &a, int b) {a = max (a, b);}
void gmin (int &a, int b) {a = min (a, b);}
using namespace lay;
signed main () {
return 0;
}
```