CLYZ 联考。鉴定为 FJOI。
A
问 \(\{1,2,\dots,n\}\) 有多少子集的 \(\gcd=G\)，\(\operatorname{lcm}=L\)。
另外地，多次询问若子集包含 \(x\) 的方案数。答案模 \(998244853\)。
\(1\le n,G,L\le 10^8\)，\(1\le q\le 5000\)，\(1\le x\le n\)。
\(\mathrm{TL}=6\mathrm{s}\)。
先解决第一个问题。
若 \(G\not\mid L\) 显然答案为 \(0\)。否则令 \(L\leftarrow \dfrac{L}{G}\)，\(n\leftarrow \left\lfloor\dfrac{n}{G}\right\rfloor\)。
也就是说 \(\gcd=1\)，\(\operatorname{lcm}=L\)。显然的是只有 \(L\) 的因子有贡献。
注意到 \(\omega(L)\le 8\)，考虑状压。
设 \(f_{i,S,T}\) 表示当前 \(S\) 集合内的质因子顶到上界，\(T\) 集合内的质因子顶到下界的方案数。
转移为 \(f_{i,S|s,T|t}\leftarrow f_{i-1,S,T}\)，\(f_{i,S,T}\leftarrow f_{i-1,S,T}\)。时间复杂度 \(O(\sigma_0(L)\cdot 2^{2\omega(L)})\)。
现在解决第二个问题。
若 \(G\not\mid x\)，答案为 \(0\)。否则令 \(x\leftarrow \dfrac{x}{G}\)。此时若 \(x\not\mid L\)，答案为 \(0\)。考虑此外的情况。
能够想到将前缀和和后缀和合并。时间复杂度 \(O(\sigma_0(L)\cdot 3^{2\omega(L)})\)。
发现合并复杂度瓶颈在于枚举子集。使用高维前缀和预处理，合并可以做到 \(O(2^{2\omega(L)})\)。
总时间复杂度 \(O(\sigma_0(L)\cdot 2^{2\omega(L)})\)。
代码好冗长。
B
问序列 \(\{a_n\}\) 有多少种合法的划分 \(\{S\}\) 满足每个 \(S_i\) 有 \(\min\le \operatorname{len}\le\max\)。答案对 \(10^9+7\) 取模。
\(n\le 5\times 10^5\)。\(\mathrm{TL}=0.5\mathrm{s}\)。
注意到 \(\min\) 不升，\(\operatorname{len}\) 单增，可以 \(O(n\log n)\) 二分出满足 \(\min\le \operatorname{len}\) 的最小 \(\operatorname{len}\)。
有两个暴力策略。枚举所有前缀的后缀 \(\max\)，或者枚举所有后缀的前缀 \(\max\)。后者直接放了 \(100\) 分。
正解是 CDQ 分治。膜拜 Logic_J_X。
C
给出两个数 \(n,m\)。你需要构造非负整数序列 \(\{a_n\}\)：
有 \(n\) 条要求形如 \((p_i,b_i,t_i)\)：若 \(\displaystyle \sum_{j=i}^{p_i}a_i<b_i\)，产生 \(t_i\) 的代价。保证 \(i\le p_i\)。
有 \(m\) 条限制形如 \((x_i,y_i,c_i)\)：\(\{a_n\}\) 必须满足 \(\displaystyle \sum_{j=x_i}^{y_i}a_i\le c_i\)。保证 \([x_i,y_i]\) 是若干 \([i,p_i]\) 的不交并。
求出最小代价。
\(n,m\le 5\times 10^5\)，\(b_i,c_i,t_i\le 10^9\)。\(\mathrm{TL}=1.5\mathrm{s}\)。
对 \(\{a_n\}\) 作前缀和，要求 \(\displaystyle \sum_{j=i}^{p_i}a_j\ge b_i\) 等价于 \(sum_{i-1}-sum_{p_i}\le -b_i\)，用差分约束系统建图 \((p_i,i-1,-b_i)\)，得到 \(n+1\) 个点的以 \(n\) 为根的外向树。
限制 \(\displaystyle \sum_{j=x_i}^{y_i}a_j\le c_i\) 等价于 \(sum_{y_i}-sum_{x_i-1}\le c_i\)，建边 \((x_i-1,y_i,c_i)\)，由于题目给出的 \([x_i,y_i]\) 的性质，建出的边一定连向自己的祖先。
图上的负环一定由一个节点 \(u\) 到其后代 \(v\) 的树边与 \(v\) 到 \(u\) 的非树边组成。称 \(u\) 到 \(v\) 的链为负环链，\(u\) 为上端点，\(v\) 为下端点。
转化为使得每条负环链至少断掉一条边的最小代价。
设 \(\operatorname{link}(x)\) 为以节点 \(x\) 为下端点的负环链的上端点的最大深度（\(dep_n=1\)），不存在则为 \(0\)。
设 \(w_x\) 为断开 \((fa_x,x)\) 的代价，\(f_{x,i}\) 为两个端点都在 \(x\) 子树内的负环链以及下端点在 \(x\) 子树内且上端点深度大于 \(i\) 的负环链都至少被断开一条边的最小代价。
- \(\operatorname{link}(x)=0\)
此时有转移方程
使用线段树合并维护。
时间复杂度 \(O(n\log n)\)？
D
*3078。
有一个无穷长的 01 序列。其中 \(\{x_n\}\) 中的位置是 \(0\)，其他均为 \(1\)。
每次可以选择一个长为奇素数的连续段翻转。问最后全为 \(1\) 的最少操作次数。
\(1\le n\le 1000\)，\(1\le x_1<x_2<\dots<x_n\le 10^7\)。AtCoder 中 \(n\le 100\)。