Day0
晚上玩恐怖游戏好吓人 \(QwQ\)
Day1 rk4
有小奖品
T1
没什么好说的
T2
给定一个等差数列，求他的各项乘积，你只需要输出其对 \(1145141\) 取模的结果。
具体的，每组给定 \(d,n,a\) 分别表示公差，长度，首项，你需要求出 \(\prod_{i=0}^{n-1} (a+i\times d) \mod 1145141\)。
非常降智好的一道题，赛时往根号分治想，然后寄掉了
我们考虑 \(d=1\) 怎么做，显然阶乘，然后判断是否包含 \(mod\) 的倍数即可，复杂度 \(O(mod)\)
然后推广到普遍情况，我们把这个式子提出来 \(d\) 变成： \(d^n\prod_{i=0}^{n-1} (\frac{a}{d}+i) \mod 1145141\)
这不就是 \(\frac{a}{d}\) 到 \(\frac{a}{d} + n - 1\) 的阶乘吗。我们得益于乘法逆元，可以直接用 \(a \times d^{-1} \mod 1145141\) 来代替
注意特判 \(d = 0\) 的情况即可，最终复杂度 \(O(T \log mod)\)，瓶颈在快速幂
T3
一条路径上有 \(n\) 个位置，有三种元素：\(slime\)，\(npc\)，\(player\)。
\(slime\) 初始会向右移动，\(npc\) 初始会向左移动，所有元素移动速度是相同的：\(1\) 单位距离每 \(1\) 单位时间。
元素的移动遇到边界会改变初始移动方向，并继续移动。
我们称 \(player\) 与 \(npc\) 为人类，\(npc\) 带有初始为 \(0\) 的能力值。
你作为 \(player\) 与 \(npc\) 有相同的移动规则，由于带有主角光环，你若出生在位置 \(i\) 初始会有 \(s_i\) 的能力值。
若有某两元素相遇，他们会开始战斗，战斗不改变移动方向，战斗总是遵循以下两种规则。
1、人类与 \(slime\) 相遇：人类总是胜利，胜利后人类能力值 \(+1\)。
2、人类与人类相遇：能力值大的获胜，若能力值相同，则 \(player\) 获胜，能力值不发生改变。
可以证明，这两条规则覆盖了所有情况。
失败的一方将被立刻移除游戏，胜利的一方将仍继续行进。
由于你是主角，你的左侧总是以 \(100\%\) 的概率刷新 \(slime\)，你的右侧总是分别以 \(50\%\) 的概率刷新 \(npc\) 或者 \(slime\)。
对于 \(1,n\) 两个特殊位置有特殊的刷新规则：\(1\) 号位置总是 \(slime\)，\(n\) 号位置总是 \(npc\)。
你需要求出来你以相同概率随机出生在 \([2,n-1]\) 的某一位置，经过 \(\infty\) 单位时间后，仍存活的概率。
你需要注意，游戏的进程总是 \(player\) 先刷新，然后以一定概率刷新 \(slime\) 和 \(npc\)，然后开始游戏。
可以证明概率总是一个有理数 \(x\over y\)，你只需要输出这个数对 \(998244353\) 取模的结果。
保证 \(s_1=s_n=0\)。
对于所有测试点满足 \(3\leq n\leq 5\times 10^5,0\leq s_i\leq 10^9\)。
一道二项式反演题
我们假设现在在考虑第 \(i\) 位，令 \(B = s_i + i - 1\) ，我们让 \(f(n)\) 表示钦定 \(n\) 个 \(slime\) 长度 \(=B + 1\) ，之后跟一个 \(npc\) 时的方案数(这里如果 \(> B+1\) 的连续段怎么办？一会再说)，我们可以知道 \(g(0) = \sum_{i>0} (-1)^{i} \binom{i}{0} f(i) = \sum_{i>0} (-1)^i f(i)\)
我们考虑怎么求 \(f(k)\) ，我们用组合数，我们先确定 \(k\) 个连续段，然后考虑往这 \(k+1\) 个位置里插入剩下的 \(n - i - 1 - k \times (B + 2)\) 个 \(slime\) (其中 \(-1\) 的原因是我们钦定的是 \(slime\) )，这里直接用插板法：把这些史莱姆插到 \(k+1\) 个空里的方案数
一些细节：由于 \(n\) 号节点始终是 \(npc\) ，我们要讨论在钦定不满足条件的连续段时是否钦定了 \(n\) 这一个 \(npc\)
复杂度分析：有人觉得这是 \(O(n^2)\) 的，但我们发现玩家在 \(i\) 位置时能力值至少为 \(i-1\) ，因此复杂度为调和级数，最终复杂度 \(O(n \log n)\)
T4
一行人，共有 \(n\) 个人，排成一排，在等待你发放矿泉水。
你会发放 \(m\) 轮矿泉水，第 \(i\) 次，你会给前 \(a_i\) 个人发放矿泉水，然后你会发放 \(b_i\) 瓶矿泉水。
具体的，你每次会一瓶一瓶的发矿泉水，每一轮发放 \(b_i\) 次。
每次，你会把矿泉水给最需要的人，即前 \(a_i\) 个人中，当前拥有的矿泉水最少的人，如果有多个人拥有数量相同，你会发给编号靠前的人。
最终，你想知道每个人获得的矿泉水数量。
\(n,m \leq 10^5\)
首先，我们看答案是单调不降的，因此我们可以线段树 \(+\) 二分，而不是树套树之类的
从来没做过在线段树某个前缀 \(or\) 区间上二分的问题，学到了
LL k;
int search(int x, int p = 1){
int l = tr[ p ].l, r = tr[ p ].r;
if(r <= x && (LL)tr[ p ].maxs * (x - l + 1) - tr[ p ].sum <= k){
k += tr[ p ].sum;
return l;
}
if(l == r) return r + 1;
PushDown(p); int mid = l + r >> 1;
if(x <= mid) return search(x, ls);
int rt = search(x, rs);
if(rt == mid + 1) return search(x, ls);
return rt;
}
大致就是判断右边如果能放就放右边，否则放左边
最终复杂度 \(O(n \log n)\)
$p.m. 杂题选讲
最朴素的是 \(3^n\) 枚举，爆炸
考虑我们如果 \(2^n\) 找两个和相同的方案，然后让第一个 \(-\) 第二个依然合法。因为题目保证 \(p < 2^n\) ，因此一定有两个子集之和 \(\mod p\) 值相同。优化成 \(O(2^n)\) ，爆炸
数据范围提示 \(meet in the middle\) ，但我们如果不知道这个和是多少不好做
哪有问题解决哪里，我们二分这个和是多少。具体的，我们考虑答案值域为 \([l,r]\) 时方案数，显然 \(> r - l + 1\) ，然后我们通过爆搜判断 \([l, mid]\) 值域内方案数是否 \(> mid - l + 1\) ，如果不满足，右边显然满足。考虑通过 \(meet in the middle\) 来判断这个东西，这里的复杂度是 \(O(2^{\frac{n}{2} \log n)\)
二分到最后我们知道了具体的值就好做了，直接找即可
最终复杂度 \(O(2^{\frac{n}{2}} \log n)\)