前两层和式还是可以 \(\mathcal O(m\log m)\) 枚举，重点考察

的计算。先做简单简化，

所以我只需要求 \(g(1,x)\) 的值。注意到一个有趣的事实：\(q\le m\)，而 \(s_i\le \lcm(S)\)，所以当 \(\lcm(S)\) 合法时，序列 \(S\) 一定合法。结合 \(\lcm\) 的性质，自然想到拆开素因子贡献。而根据上述事实，素因子的贡献互不影响，可以直接将素因子贡献乘起来得到答案。因此

可以 \(\mathcal O(m\log\log m\log n)\) 求解（官方题解的复杂度应该有误）。注意到 \(\sum p^i\) 是 \(\mathcal O(m)\) 级别的，通过线性筛预处理自然数幂可以做到 \(\mathcal O(m\log\log m)\)，则总复杂度为 \(\mathcal O(m\log m)\)。

\(\mathscr{Topic}\rightarrow\) 多项式 \((4/7)\)

\(\mathscr{A.}\) 「CF 286E」Ladies' Shop ^

??众所周知，^ 表示做过的题（“跳”，很形象.jpg）。

\(\mathscr{B}.\) 「CF 960G」Bandit Blues

??水题。和建筑师一样的。。

??然后我为了图省事儿一个「斯特林数-列」+ 暴力枚举最大值位置莽上去，因为模数忘记改调了半天。??

\(\mathscr{C}.\) 「CF 986D」Perfect Encoding

??水，但高精只能用 Pascal 卡过（在省事的前提下）。

\(\mathscr{D}.\) 「CF 623E」Transforming Sequence ^

??。DP 选择本身比较无序，所以可以倍增。但是 MTT。

\(\mathscr{E}.\) 「AGC 021F」Trinity *!

??Link.

??还没写 qwq。

\(\mathscr{Summary}\sim6.16\)

??今天 arc 是不是有活动啊。

\(\mathscr{Contest}\) \((2/3)\)

??Contest.

??对于题目质量只能不予置评，被错大样例整死了。

??怎么大家都没有质疑精神呢？

\(\mathscr{A}.\) 小学生物理题

??有 \(n+1\) 条导线串联了节点 \(0,1,\dots,n+1\)，其中 \(0\) 在负无穷远处，\(n+1\) 在正无穷远处，其余点用坐标描述。现在有恰一条导线断路，站在一个节点上，检查该节点是否与 \(0\) 联通的代价为 \(d_i\)，在节点间行走的代价为走过的距离，修复第 \(i\) 条导线的代价为 \(f_i\)。求从 \(1\) 出发，最坏情况下修复好导线的最小代价。

??\(n\le3\times10^3\)。

??Tag: 「A.DP-单调队列优化」

??发现肯定不会检查 \(0\) 和 \(n+1\)，所以可以把 \(0\) 挪到 \(1\) 的位置，\(n+1\) 挪到 \(n\) 的位置，初始时从 \(0\) 出发，这样就没有“无穷远”的特殊性了。先想暴力，令 \(f(l,r,0/1)\) 表示已知断路位置在节点 \(l,r\) 之间，现在站在 \(l/r\) 时，……的最小代价。那么

注意到若 \([l,r]\subseteq [L,R]\)，则 \(f(l,r,t)\le f(L,R,t)\)。于是当固定 \(l\) 或 \(r\) 时 \(\max\) 取的项关于 \(r\) 或 \(l\) 具有单调性。指针维护 \(\max\) 取值分界点，单调队列维护可选值的最小值即可。复杂度 \(\mathcal O(n^2)\)。

??被卡常了，懒得卡 qwq。

\(\mathscr{B}.\) 数轴变换 *

??维护一根数轴。初始时 \(0\) 为黑色，其余整点为白色。进行 \(q\) 次操作：

1. 单点染黑。
2. 将所有黑点附近距离不超过 \(x\) 的整点染黑。
3. 反转区间 \([l,r]\)。
4. 回退到历史状态。
5. 单点查询。

??\(q\le2\times10^5\)，坐标不会爆 long long。

??Tag: 「A.数据结构-可持久化平衡数」

??由 \(2\) 操作启发，注意到一个点被染黑多次并不影响答案，尝试维护差分序列。由于 \(+1\) 和 \(-1\) 在 2 中的移动方向不同，所以得用分开维护它们。现在 \(1,2,5\) 理论上好做了，\(4\) 加个持久化问题不大。问题在于 \(3\)，据说是一个 trick：在左右加无实际效果的 \(+1\cdots-1\cdots\) 使得 \([l,r]\) 内的差分标记构成匹配括号串，然后将括号串翻转（不是单纯 reverse，是真的“翻”）。总之 \(\mathcal O(q\log q)\) 能做。

\(\mathscr{C}.\) 中学生物理题 *!

??这是值得补的！

\(\mathscr{Summary}\sim6.17\)

\(\mathscr{Summary}\sim6.18\)

\(\mathscr{Summary}\sim6.19\)

\(\mathscr{Summary}\sim6.20\)

??前几天因为以学考为主的破事儿耽搁了，也许会补上。（咕

\(\mathscr{Contest}~(3/3)\)

??Contest.

??问题是，最后 \(40~\text{min}\) 才发现 A 是签到真的合理吗？

\(\mathscr{A}.\) 益智游戏

??把 \(n\times n\) 的网格图中所有 \(n^2\) 个格子各自划分为 \(2\times 2\) 的小网格，并在其中放上一块骨牌。给出初始骨牌放置方案，改变 \((i,j)\) 上骨牌方向的代价为 \(a_{i,j}\)，求最少的代价，使得不存在一个 \(2\times2\) 的小网格的对角线都被骨牌覆盖。

??\(n\le2\times10^3\)。

??Tags:「A.DP-杂项」「C.性质/结论」

??（上面的题意写得像狗屁，但我懒死了。）

??手玩一下结论，发现左置骨牌的左侧一定是左置骨牌，其余方向结论类似。然后发现：

??对分割点的上下左右四部分分别 DP 求最优方案即可。复杂度 \(\mathcal O(n^2)\)。

\(\mathscr{B}.\) 华为 *

??给定 \(n,m,p\) 与 \(T\) 此询问 \((x_i,y_i)\)，初始时 \(x=y=0\)，每次操作以 \(p\) 的概率令 \(x\gets (x+1)\bmod n\)，否则令 \(y\gets (y+1)\bmod m\)，求 \(x=x_i\land y=y_i\) 时的期望操作次数。答案模 \(998244353\)。

??\(n\le10^9\)，\(m,T\le400\)。

??Tags: 「A.多项式」「B.向量/矩阵优化」

??\(\mathcal O((n+m)^3)\) 的就不说了。注意到 \(n\) 的量级与 \(m\) 不同，令 \(f(i,j)\) 表示 \(x=i,y=j\) 出发逆向操作到 \(x=y=0\) 的期望操作次数，尝试强行拆开 \(m\) 方向上（行上）的转移环，观察列上 \(f(i,\star)\) 整体的变化。令 \(q=1-p\) 为操作施加到 \(y\) 的概率。因为

去消除 \(f(x,y-1)\) 这项，直接枚举 \((x,y)\) 最终从哪个 \(y'\) 走到 \((x-1,y')\)，那么

令 \(F_x(z)=\sum_{i=0}^{m-1}f(x,i)z^i\)，那么

其中 \(\times\) 是模 \(z^m\) 意义下的循环卷积。注意到这是对 \(F\) 的线性变换，立马想到矩阵加速。令

则 \(f(x,y)=[z^y](V^x\begin{bmatrix}F_0(z) & 1\end{bmatrix}^T)^{(1)}\)。

??问题是，我们并不知道 \(F_0(z)\)。结合暴力做法，直接拿出 \(F_{n-1}(z)\) 表示 \(F_0(z)\)，解一解方程即可。复杂度 \(\mathcal O(m^3+Tm\log m\log n)\)。

\(\mathscr{C.}\) 区间距离 *

??给定 \(a_{1..n},b_{1..n}\)，\(q\) 次询问，每次给出 \(p_1,p_2,l\)，求出

??\(n\le10^5\)，\(q\le10^6\)，\(1\le a_i,b_i\le V=5\)。

??Tag: 「A.分块」

??暴力循环可以过十万方，并且我发现三目有时比一维 int 数组寻址快。

??分块，就每 \(\omega\) 一块，因为询问涉及到对 \(a\) 的位移，所以块小一点可以以更小的损失对齐整块。预处理每个小位移 \(r\in[0,\omega)\)，整块位移 \(R\in[-n/\omega,n/\omega]\) 的情况下，\(a\) 的前 \(k\) 个块与 \(b\) 的前 \(k\) 个块对应的答案。把 \(|x-y|\) 拆成 \(\sum_c [[x\le c]\neq[y\le c]]\) 数一数 bit 即可。复杂度 \(\mathcal O(Vn^2/\omega+q\omega)\)。

\(\mathscr{Summary}\sim6.21\)

\(\mathscr{Contest}~(3/3)\)

??Contest.

??从头暴力到尾，比较稳健就是了。

??个人感觉 T2 T3 部分分不大合理，像我这种纯暴力选手得分太多了。（

??T1 比较尴尬，写了个根号（而且可能是伪的）算法然后开始卡 \(\log\)，没想到正解是 polylog 的。掉坑里走不出来了。

\(\mathscr{A.}\) 给国的道路 *

??给定无向图 \(G\)，结点 \(u\) 有点权 \(a_u\)。\(E_G\) 初始为 \(\varnothing\)，但是提供了可选的边集 \(E=\{(u,v,s)\}\)。当 \(G\) 中 \(u,v\) 不连通且 \(u,v\) 连通块点权和 \(\ge s\) 时，\((u,v,s)\) 可加入 \(E_G\)。求最长的、再字典序最小的边加入方案。

??\(n\le10^5\)，\(m\le2\times10^5\)，\(a_i,s\le10^6\)。

??Tags: 「A.并查集」「B.Tricks」

??设边 \((u,v,s)\) 当前还需要 \(r\) 的点权和才能加入 \(G\)，在每个连通块上用堆维护二元组 \((r/2,(u,v,s))\)。注意我们对 \(r\) 的更新是惰性的：拿出最小的 \((r/2,(u,v,s))\)，若 \(r/2\le 0\)，重新算一遍得到一个 \(r'\)，根据 \(r'\) 再来决策是否加入边。每条边最多被误判（拿出来又放回去）\(\mathcal O(\log V)\) 次。Splay 实现启发式合并可以做到 \(\mathcal O(n(\log n+\log V))\)。

??（然后发现 pb_ds 的 tree<..., splay_tree_tag, ...> 跑出来还没 std::set 快。）

\(\mathscr{B.}\) 给国与时光机 *

??考虑数轴上的整点 \(0..2n+1\)，其中 \(1..2n\) 被 \(n\) 个传送门两两配对。走 入一个点时，必须 传送 到另一个点。从 \(0\) 出发走到 \(2n+1\)，已知 \(\{(a_i-1,a_i)\}_{i=1}^m\) 是所有被走过的线段，构造配对方案或声明无解。

??\(n\le10^5\)。

??Tag: 「A.构造」

??把 \(0..2n\) 分为 \(A,N,L,R\) 四个集合，分别表示 \(x\) 两边都走过/都没走过/只走过左/只走过右。显然传送门只能在 \(A^2,N^2,L\times R\) 里选。\(N^2\) 随意就好，如果 \(2\nmid|N|\) 则不合法。结合 \(m=2n+1\) 的暴力，可知 \(2\nmid|A|\) 不合法；\(4\mid|A|\) 时 \(A\) 可以四个一组交错配完，\(L,R\) 相邻配；否则 \(|A|=4k+2\)，留两个 LR 配对，把夹着 LR 的一对 AA 配对即可。复杂度 \(\mathcal O(n)\)。

\(\mathscr{C.}\) 给国与赌场 *

??卢老爷拿着 \(\frac{a}{b}<1\) 块钱准备赢到不少于 \(1\) 块钱。每次他可以投注任意正实数金额 \(r\in(0,\frac{a}{b}]\)，但必须不小于上次投注金额，此后以 \(p\) 的概率得到 \(2r\) 块钱，否则血本无归。求最优策略下达到目标的概率。

??\(b\le10^6\)，\(p<\frac{1}{2}\)。

??Tags: 「C.思维」「C.性质/结论」

??一个比较好猜也比较好证的结论：每次投注现有本钱 \(x\) 的二进制小数表示下的最低 bit。这是因为若投注的不是最低 bit，则无论赢钱与否，最低 bit 都没法再使用，也没法对 \(\ge1\) 产生任何贡献。

??那么当 \(a/b\) 是有限小数时就可以直接模拟了，否则，对于完全不会数学的兔来说还是非常困难。

??然后我被神谕了结论：我们还有一种贪心策略：若 \(x<\frac{1}{2}\)，all in；否则投注 \(1-x\)。注意到上一个结论的证明其实可以说明要不要求投注递增这一要求，我们的策略都是优的，所以这里直接忽略。

??设在这种策略下，\(f(x)\) 表示本金 \(x\) 的获胜概率，则

? ?可以证明这种策略与 lowbit 策略等价。如图：

单次迭代可以把大三角形拍成两个小三角形（注意点的开闭），足够的迭代后每个位置的取值都是自己的 lowbit。

??拿着 \(f(x)\) 做就比较好办了。设 \(f(a/b)=z\)，迭代 \(f(*/b)=kz+b\)，得到一个 \(\rho\) 形迭代过程，通过环或者 \(a=0\) 的位置把 \(z\) 解出来即可。复杂度 \(\mathcal O(b)\)。

\(\mathscr{Summary}\sim6.22\)

??【洛天依AI】贝加尔湖畔【你清澈又神秘】_哔哩哔哩_bilibili

??都给我去听！！！！！！！！！

\(\mathscr{Topic}\rightarrow\) 思维向杂题 \((9/9)\)

??注：本节的星号 * 标记可能有歧义，毕竟怎么都浅听过一遍讨论的。因此将其弃用。

\(\mathscr{A.}\) 「CF 1458C」Latin Square

??Link & Submission.

??Tag: 「B.Tricks」

??Trick: 注意到对 \(p\) 求逆相当于 \((i,p_i)\rightarrow (p_i,i)\)，那么把 \(p_i\) 也当作一维坐标。

??所以需要维护三维坐标集合 \(\{(x,y,z)\}\)，支持一个坐标整体位移、两维坐标整体交换。拿常数个标记就能 \(\mathcal O(1)\) 维护。所以复杂度为 \(\mathcal O(\sum n^2+\sum m)\)。

\(\mathscr{B.}\) 「ICPC EC-Final 2020」「Gym 103069C」Random Shuffle

??Link & Submission.

??Tag: 「A.Gauss 消元」「C.性质/结论」

??这个 xor-shift 发生器生成的数的每个 bit 必然是种子的 \(64\) 个 bit 的一个线性组合。通过反向还原 \(a\) 可以得到第 \(i\) 次生成的数 \(x_i\) 模 \(i\) 所得余数 \(r_i\)，即 \(x_i=r_i+k\cdot i~(k\in\mathbb N)\)。于是，我们可以借此确定 \(x_i\) 低于 \(i\) 的 lowbit 的 bit 与 \(r_i\) 的对应 bit 相等，继而构造关于 \(x\) 的 bit 的线性方程组。最贫困的 \(n=50\) 时，我们会得到 \(47\) 个方程，除去线性相关的东西大概有不超过 \(20\) 个自由元，暴力枚举它们的取值 check 一下即可。

??设方程有 \(c\) 个自由元，\(\omega=64\) 为 bit 数，复杂度最坏为 \(\mathcal O(2^c(\omega+n))\)。需要位运算稍精细实现。

\(\mathscr{C.}\) 「THUPC 2021」「洛谷 P7606」混乱邪恶

??Link & Submission.

??Tags: 「A.DP-数据结构优化 DP」「B.std::bitset」

??背包是一个 \(n\times n\times n\times m\times m\) 的 TF 状态，std::bitset 扬掉最后一维，经典随机化根号 trick 扬掉两个 \(\sqrt n\)，选一选阈值，\(\mathcal O(\frac{n^2m^2}{\omega})\)，当然至少有个枚举方向的 \(6\) 的常数。

\(\mathscr{D.}\) 「JOISC 2022」「UOJ #731」制作团子 3

??Link & Submission.

??Tags: 「A.构造」「C.非传统-交互题」（为了不污染 tag，带「构造」的默认带「思维」。）

??如何判断一个集合 \(S\) 是否存在重复的团子？——询问 \(U\setminus S\)，若回答 \(a=m-1\)，则表明 \(S\) 无重复团子。

??进一步，思考 \(a\) 的意义：其表示 \(S\) 内出现最多的团子数量。

??猜测 \(5\times10^4=5nm=\lceil\log m\rceil nm\)，二分？利用鸽巢原理，可以简单得到一个基于增量法的构造：令 \(m\) 个集合 \(S_{1..m}\) 为 \(m\) 串团子，尝试将当前团子 \(x\) 放入其中一个使其仍合法。每次取可能集合的一半 \(\mathcal T\)，得到 \(\{x\}\cup\{S\in \mathcal T\}\) 中出现最多的团子数量 \(a\)。若 \(a\le |\mathcal T|\)，则 \(\mathcal T\) 中存在一个可加入 \(x\) 的集合；否则 \(\mathcal S\setminus \mathcal T\) 中存在，递归询问就好。操作次数为 \(\mathcal O(nm\log m)\)。

\(\mathscr{E.}\) 「集训队互测 2022」Were You Last @

??@ 是嘴巴，表示口糊，因为 OJ 上莫得。

??交互题。实现函数 bool WereYouLast(int n, int m)，其返回状态能且仅能依赖于 \(n,m\) 以及交互库提供的 \(m\) 个 bit 长的寄存器。且每次调用时，仅能对其中不超过 \(6\) 个 bit 进行读和（或）写。要求其恰好在第 \(n\) 次调用时返回 true。

??\(m=10^5\)，\(n=2^k\le2^{26}\)，\(k\in\mathbb N\)。

??Tags: 「A.构造」「C.非传统-交互题」

??我确实编不出 motivation 了，总之我们用 \(5+26\) 个 bit 构成了一个 pointer 和一个 pool。pointer 指向 pool 的一个位置 \(p\)。则函数行为如下：

1. 读出 \(p\)。
   • 若 \(p=\log n\)，返回 true。
2. 读出 \(p\) 指向 bit 的值 \(x\)。
   • 若 \(x=0\)，令 \(p\gets0\)；
   • 否则 \(x=1\)，令 \(p\gets p+1\)。
3. 令 \(x\gets\lnot x\)。
4. 返回 false。

不难证明，\(p\) 第一次取到 \(p_0\) 时，是第 \(2^{p_0}\) 次调用。这真的“很经典”吗……

\(\mathscr{F.}\) 「CF 1500D」Tiles for Bathroom

??Link & Submission.

??Tag: 「A.DP-杂项」

??对于 \(k\)，显然可以差分。我们只需要对于 \((i,j)\)，求出以其为右下角的最大合法方阵即可。进一步，可以转化为求 \(q\) 远切比雪夫距离。直接在每个位置维护一个前 \(q\) 近集合，在 \((i,j)\) 合并 \((i-1,j-1),(i-1,j),(i,j-1)\) 的集合并贡献答案。暴躁实现的复杂度是 \(\mathcal O(n^2q\log q)\)。

\(\mathscr{G.}\) 「LOCAL ?」LCM @

??给定序列 \(A=\{a_i\}_{i=1}^n\)，求字典序最小的 \(B=\{b_i\}_{i=1}^n\)，使得 \(\forall i,~b_i\mid a_i\) 且 \(\lcm A=\lcm B\)。

??\(n\le10^4\)，\(a_i\le10^{18}\)。

??显然的贪心：对于每个 \(\lcm A\) 中的 \(p^k\)，把它放在最后一个 \(A\) 中的出现位置。

??素因数分解？这数据范围连 Pollard-Rho 都不放过。考虑从后往前增量法构造 \(B\)。对于当前的 \(i\)，令 \(t\gets a_i\)，枚举 \(j>i\) 并令 \(t\gets t/\gcd(t,b_i)\)，继而得到 \(a_i\) 中取到目前 \(\lcm\) 的素因子集合。把这些素因子幂的乘积作为 \(b_i\)，再将 \(j>i\) 的 \(b_j\) 除掉 \(\gcd(b_i,b_j)\)，因为 \(b_j\) 这一部分素因子的指数不足以贡献 \(\lcm\)，自然是扔掉更优啦。这是一个 \(\mathcal O(n^2\log V)\) 的算法，还是过不了。

??接下来是优化。对于求 \(t\) 的过程，类似 Pollard-Rho，先累积所有 \(b_i\) 再取 \(\gcd\)。令 \(s=\prod_{j>i}b_j\bmod a_i\)，那么 \(s\) 的素因子集是 \(t\) 的超集（但是它们的幂不一定不小于 \(t\) 中的幂）。则不断迭代令 \(t\gets t\gcd(s,a_i),a_i\gets a_i/\gcd(s,a_i)\) 就能得到 \(t\)。这里也许可以优化到单 \(\log\)。

??对于 \(b_j\) 除因子的过程，注意到 \(B\) 是互素的，那么顶多有 \(\log b_i\) 个不同的位置会因除法变化；而一个数最多被除 \(\log\) 次。二分之类的快速找出这些位置除掉 \(\gcd\)。最终可以做到 \(\mathcal O(n^2+n\log n\log V)\)。可能有个 \(\mathcal O(n\log^2V)\)。

??嘴巴真舒服。

\(\mathscr{H.}\) 「洛谷 P6383」Resurrection

??Link & Submission.

??Tags: 「A.DP-树上 DP」「C.性质/结论」

??所以我觉得讨论题真的可能糟蹋了好题。耳朵顺走一个结论啥事没有。

??先来研究 \(G\) 合法的条件。有以下几个必要条件是容易发现的：

• \(G\) 是树。
• 以 \(n\) 为根，\(G\) 中结点 \(u\) 的父亲是 \(T\) 中结点 \(u\) 的父亲。
• \(G\) 中的父子连边在 \(T\) 上对应的路径，若路径共线，则不会交而不含。

??喜闻乐见，这些条件和起来就充分了。

??对这个结论计数：令 \(f(u,i)\) 表示 \(u\) 选完自己的父亲后，留下了 \(i\) 个严格祖先让孩子们可以选时，\(u\) 子树内的方案数。那么

随便优化一下做到 \(\mathcal O(n^2)\)。

\(\mathscr{I.}\) 「CF 1586F」Defender of Childhood Dreams ^

\(\mathscr{Summary}\sim6.23\)

\(\mathscr{Contest}~(3/3)\)

??Contest.

??T1 切得比较迅速，顺便醒了瞌睡。T2 想起那啥 \(\gcd\) 矩阵，尝试构造上三角化之类的矩阵构造得脑袋消失。T3 冲了暴力，知道是 DDP 但根本没细想。问题主要是“尝试构造”的过程效率真的低。

\(\mathscr{A.}\) 寄

??给定一棵含 \(n\) 个结点的带权树和 \(m\) 个关键点 \(a_{1..m}\)，选定一个点集 \(b_{1..k}\)，最小化

??\(n\le3\times10^3\)。

??Tag: 「A.DP-树上 DP」

??最小化最小 \(=\) 最小化任意。每个 \(b\) 可以随意钦定覆盖点，但需要支付覆盖的连通块个数个 \(C\) 的代价。可以证明不会影响最有解的值。于是，令 \(f(u,v)\) 表示钦定 \(u\) 被 \(v\)（任何一个点）覆盖时，\(u\) 子树内的距离与支付的 \(C\) 之和。那么

\(\mathcal O(n^2)\) 很简洁地解决掉。

\(\mathscr{B.}\) 摆 *

??给定 \(n,c\)，构造矩阵 \(A=\{a_{ij}\}\)，其中

求 \(\det A\bmod 998244353\)。

??\(n\le10^{11}\)，\(\text{TL}=6\text s\)。

??Tags: 「A.数学-数学推导」「A.数学-线性代数」「B.Tricks」「C.性质/结论」

??注意到 \(A\) 的主对角线的下方全部是 \(c\)。通过相邻行作差，可以使其成为上海森堡矩阵。每行除一个 \(c-1\)，令 \(v=\frac{c}{c-1}\)，那么现在 \(A\) 长成

（右上部分有值，左下部分全 \(0\)。）注意上海森堡矩阵 \(\det\) 的特殊性，对于其定义式所枚举的 \(\sigma\) 中，每个置换环必然取一堆 \(v\)，最后取一个主对角线及以上的位置。设前 \(i\) 行 \(i\) 列的主子式为 \(f_i\)，那么

令 \(g=\Delta f\)，那么

??我们只需要求 \(f_n\)，即 \(g\) 的前缀和。没见过的 trick：这玩意儿可以魔改杜教筛实现的。观察杜教筛的作用式

理论上，\(t,h\) 好求前缀和就行，这并不完全依赖与 \(g\) 的积性。对于本题，构造 \(t(n)=[n=1]v-[n\neq 1]\) 类似物，就能筛了。

??但 \(\mathcal O(n^{2/3})\) 依赖于预处理的线性。注意到 \(g(n)\) 只与 \(\{\alpha_p(n)\}\) 有关，精细地减少对 \(\{\alpha_p(n)\}\) 相同的 \(n\) 的点值计算就能极大地优化速度。复杂度大概就是 \(\mathcal O(n^{2/3})\)。

\(\mathscr{C.}\) 润 *@

??给定函数

维护 \(01\) 序列 \(a_{1..n}\)，令 \(v(l,r)=\sum_{i=l}^r2^{i-l}a_i\)，进行 \(q\) 此操作：

1. \(\forall i\in[l,r],~a_i\gets1-a_i\).
2. \(\forall i\in[l,r],~a_i\gets0\);
3. \(\forall i\in[l,r],~a_i\gets1\);
4. 求出 \(f(v(l,r))\)。

??\(n,q\le10^5\)。

??Tag: 「A.DP-动态 DP」

??可以看出是 DDP。注意这个贡献的转移形式形如 \(\sum k2^{k-1}\rightarrow\sum(k+1)2^k\)，令 \(s=\sum 2^{k-1}\)，\(a=\sum k2^{k-1}\)，就有 \(s'=2s\)，\(a'=2(a+s)\)，构造出了合理的线性变换。

??因此，令 \(\begin{bmatrix}z & o & s & a\end{bmatrix}^T\) 为状态向量。表示考虑了一段前缀，有 \(z\) 种递归末尾进位，\(o\) 中不进位，\(s,a\) 意义如上。分别构造 \(01\) 的转移阵即可。

??不过，对于 \(v(l,r)=2^k\)，\(\log\) 的取整情况会有偏差。所以需要找到后缀 \(00\cdots01\) 的位置，特殊地转移一下。复杂度 \(\mathcal O(q\log n)\) 带 \(4^3\)。