20220305
ABC242F(二项式反演的进一步理解)
题意：
给定一个 \(n*m\) 的矩阵，需要放
\(a\) 个白块 \(b\) 个黑块，让它们互不侵犯，\(n,m\leq 50\) 。
最开始看到这道题以为又要挑战 \(\text{npc}\)
了，仔细一看互不侵犯的定义，是不能放在同一行或同一列。
思考：
很有意思的容斥题，考虑枚举白色占了多大的地盘，设 \(f[i][j]\) 表示允许白色占用了 \(i\) 行 \(j\) 列的方案数，然后组合数容斥。我们可以设
\(g[i][j]\) 为白色恰好占用 \(i\) 行 \(j\)
列的方案数，考虑列出二项式反演的式子。思考 \(f,g\) 的关系，这是一类高维容斥问题。
结论如下： \[
g[i][j] = f[i][j] - \sum\limits_{x\leq i,y\leq j,x+y \neq i+j }
\tbinom{i}{x} \times \tbinom{j}{y} \times g[x][y]
\] 理解这个式子不难，就是减去恰好被占用的部分，注意容斥系数。
我们考虑能不能不用 \(g\)
参与这个式子。
回想线性的二项式反演问题，我们有式子： \[
f(n) = \sum\limits_{i=n}^{m} \tbinom{i}{n} \times g(i) \Leftrightarrow
g(n) = \sum\limits_{i=n}^{m} (-1)^{n-i}\times\tbinom{i}{n} \times f(i)
\] 其中 \(f(n)\) 表示钦定满足
\(n\) 个条件的方案数。\(g(n)\) 表示恰好满足 \(n\) 的条件的方案数。
左边很好理解，就是钦定 \(n\)
个条件满足的方案数就是从满足 \(i\)
个条件的方案中选出 \(n\)
个钦定满足。
右边可以稍微变换一下以便理解 \[
g(n) = f(n) - \sum\limits_{i=n+1}^{m} \tbinom{i}{n} g(i)
\] 就是钦定 \(i\)
个的情况减去恰好有大于 \(i\)
个的情况乘上一个组合数，这和上面那个二维的很类似。
给出高位二项式反演公式： \[
g(n_1,n_2,⋯,n_m)=∑\limits_{k_i = 0}^{n_i}
∏\limits_{i=1}^{m}\tbinom{n_i}{k_i}f(k_1,k_2,⋯,k_m)
\]
\[
\ \ \ \ \ \ \ \ \ \ \ \Updownarrow
\]
\[
f(n_1,n_2,⋯,n_m)=∑\limits_{k_i=0}^{n_i}∏\limits_{i=1}^{m}(−1)^{n_i−k_i}\tbinom{n_i}{k_i}
g(k_1,k_2,⋯,k_m)
\]
第一个二维式子和第二个一维式子很类似，所以考虑推出 \(f,g\) 的关系。 \[
f(n,m) = \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{m} g(i,j) \times
\tbinom{n}{i} \times \tbinom{m}{j}
\] 组合解释是钦定 \(n\) 行 \(m\) 列可以被占用的方案数就是先从其中选出
\(i\) 行 \(j\) 列。然后计算恰好这么多被占用的方案数。
因为行和列是有标号的。
直接代公式有 \[
g(n,m) = \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{m} (-1)^{n-i+m-j}
\tbinom{n}{i}\times \tbinom{m}{j}\times f(i,j)
\] 结束。
ABC242H(初步理解 min-max
容斥)
题意：
给定 \(m\) 条线段，一个长度为 \(n\)
的数轴，每次随机选一条把数轴上对应位置涂黑，问全部涂黑的期望选择次数。
思考：
记 \(E(i)\) 表示第 \(i\) 个格子被涂黑的期望时间。记 \(E(S)\) 表示集合 \(S\)
全部被涂黑的期望时间，也就是所有格子中被涂黑时间的最大值，\(E'(S)\) 表示集合 \(S\)
中任意一个被涂黑的期望时间，即最小值。
显然 \(E(S) \neq \max\limits_{i\in S}
(E(i))\) ，因为期望只有线性性，\(max,min\) 是非线性操作。
但是我们发现一件事 \(\max(S) =
\sum\limits_{T \subseteq S} (-1)^{|T| - 1} \min(T)\) ，即 \(\text{min-max}\)
容斥的公式在期望意义下也成立。
而对这道题来说，计算一个集合的最小值是容易的，只需要计算出有多少个包含任意一个元素的线段就行了。
我们设 \(dp[i][j][k][0/1]\)
表示考虑到第 \(i\) 个位置，上一个位置为
\(j\) ，已经包含 \(k\)
条线段的方案数，集合大小为奇数或偶数的方案数，转移可以预处理 \([l,r]\) 会新增多少线段，做到 \(O(1)\) ，事实上最后一维可以省掉，直接带系数转移就行。
20220309
haltoj128
思考：
欧拉图计数相关问题。关于无向欧拉图有一个结论，欧拉子图的个数为 \(2^{m-n+c}\)
个，也就是其生成森林中非树边组成的集合个数，公式中 \(c\) 代表连通块个数。
理解比较容易，考虑构造方案，任意一个非树边集合会唯一对应一种合法方案，选一条非树边则将它覆盖的树边状态反转（选变为不选，不选变为选），可以得到唯一合法方案。
这个选非树边集合的方式给这道题目带来了启发。然而这种类似异或的方式并不便于统计
\(|S|^2\)
这种东西。我们考虑它的组合意义。发现其组合意义为每对边在同一子图便贡献两次，一条边在某一子图贡献一次。
一条边的情况是简单的，考虑两条边。
两条非树边是可以任选的，这一部分答案为 \(k
* (k-1) * 2^{k-2}\) ，因为已经钦定这两边要选，其它的任意选。
一条非树边和一条树边的贡献可以分两种情况，分别是树边是否受到非树边影响。不受影响答案为
\((k-cover[v]) * 2^{k-2}\) ，\(cover[v]\) 影响这条树边的非树边条数，\(k-2\)
因为钦定了选择的非树边要选，并且影响这条树边的边有一个的选择情况是不能任意，因为要让树边被选择。
如果受到非树边影响，那么答案也为 \(cover[v]
* 2^{k-2}\) ，但如果 \(cover[v] =
1\) ，那么答案为 \(2^{k-1}\) 。理解方式类似。
两条树边的情况，考虑影响这两条树边的边集，我们断言如果边集完全相同，那么答案为
\(2^{k-1}\) ，否则答案为 \(2^{k-2}\) ，边集完全相同的情况不难理解，如果不完全相同，我们在每条边特有的部分钦定一个来控制该边，所以答案为
\(2^{k-2}\) 。如果是包含关系，先钦定里面的，再钦定外面的即可。
如果要选择树边，记得不要考虑 \(cover[v] =
0\) 的边。计算 \(cover\)
可以树上前缀和，对于两条非树边，需要统计边集相同的个数，这个可以异或哈希，取
\(2^{63}\)
为上界，做双哈希，错误概率在本题数据规模下小于 \(10^{-9}\) 。
haltoj132(分治NTT的思路)
思考：
假设不考虑 \('>'\) ，即令
\('>'\)
为无限制，那么序列会被 \('>'\)
划分为若干段，记每一段的长度为 \(a\) ，那么答案为 \[
\dfrac{n!}{\prod a_i !}
\] 我们考虑容斥，枚举一个子集表示那些位置上的 \('>'\) 强制为 \('<'\) ，也就是不合法的情况，然后就可以用总数减去这些不合法情况得到答案。
上面的那个 \(n!\)
在做转移的时候很麻烦，先不管。
设 \(dp[i]\) 表示对前 \(i\) 个符号做容斥，考虑到第 \(i\) 个符号后的数字的结果。
注意到这里 \(dp[i] \times (i+1)!\)
也就是前缀 \(s_i\) 的答案。
顺便设 \(f_i\) 表示前 \(i\) 个符号中 \('>'\) 的个数。
显然有 \(dp[0] = 1\)
我们得到以下式子： \[
dp[i] = (-1)^{f_i}\times \dfrac{1}{(i+1)!} +\sum\limits_{s_j =
'>',j\in[1,i]} dp[j-1] \times (-1)^{f_{i}-f_{j}}
\times\dfrac{1}{(i-j+1)}!
\] 考虑如何理解这个式子。
我们枚举上一个不受限制的位置 \(j\) ，然后乘上对应的容斥系数和计算转移系数，最后加上全部受限制的情况。
因为要优化，所以把式子小小的变一下： \[
dp[i] = (-1)^{f_i}\times \dfrac{1}{(i+1)!} +\sum\limits_{s_{j+1} =
'>',j\in[0,i-1]} dp[j] \times (-1)^{f_{i}-f_{j+1}}
\times\dfrac{1}{(i-j)}!
\] 传说中的分治 \(NTT\)
可以解决这一类 \(dp\)
的优化问题，它的核心思路大概是这样的：
分治 \(NTT\)
解决形如这样的问题：
假设要求的函数为 \(f\) ，有另一个函数
\(g\) 。
满足 \(f(i) = \sum\limits_{j\ < i} f(j)
\times g(i-j)\) 。
类似于 \(\text{CDQ}\)
一样，考虑左边对右边的贡献即可，容易发现这是一个好做的卷积形式。
对于这道题来说，\(-1\)
的次幂可以被拆到两边，剩下的事情有手就行。
收获
容斥原理可以解决这样一类问题，有一个全集 \(S\) ，\(|S|\) 好求，现在有若干属性 \(p_i\) ，构成集合 \(T\) ，需要求满足属性集合 \(T\)
的元素个数。并且可以很容易求出这样一种情况的答案：限定某些属性不满足，其它属性不做要求。
20220320
HaltOJ 7
思考：
想一下小学的时候做过的奥数题，一个圆里画 \(n\) 条线最多分成几部分，答案是 \(n*(n+1)/2 +
1\) 。再考虑下平行线和多点共线的情况，发现答案只和每个交点的情况和交点个数有关。手玩一下可以发现，在逐个加入直线的情况下，部分的个数增量为此条直线和其它所有直线交点个数
\(x\) ，再加上 \(1\) ，注意，相同交点只算一个。
证明可以参考平面欧拉定理，此处不做赘述。
所以我们模拟这个过程，每次加入一条直线判断新增了多少交点，具体可以先暴力枚举直线，求出所有交点之后带上
\(eps\) 去重。然后发现 \(y\) 只和 \(x\)
有关，所以只用计算一个。然后我们发现如果按照斜率为第一关键字，截距为第二关键字排序加入线段，那么
\(x\) 是一个相当优美的形式 \(\dfrac{j-b}{a-i}\) ，\(a,b\) 表示当前线段的斜率和截距，\(i,j\) 表示枚举的线段的斜率和截距，\(i,j\)
的取值都连续，所以这个式子中，分母会取遍 \([1,i]\) ，分子会取遍 \([-b,B-j-1]\) ，正负数分开考虑，现在问题变成了问
\(\dfrac{[1,x]}{[1,y]}\)
中有多少个不同的数，\(A^2\)
预处理，\(O(1)\)
回答即可，约定每个数在最简分数被统计。
可以莫比乌斯反演优化，这个可以很方便的转化成 \([gcd(x,y)=1]\) 的形式并整除分块计算，可以
\(n\sqrt n\) ，但没必要。
HaltOJ8
思考
这道题出出来就展现出对直接 \(dp\)
的恶意，无论那种合并方法都无法解决这个问题。我们不妨另辟蹊径，考虑字符串的另一种生成方式——插入。
具体的，我们将不同的花视为不同字符，那么我们需要生成一个字符串，相邻字符不同，每个字符个数指定。
我们发现当前的插入方式仅仅受到当前相同字符位置个数的限制，所以设
\(f_i\) 表示考虑到现在，有 \(i\) 个字符相同位置的方案数。
转移可以枚举当前字符划分为多少段，其中有多少段插入相同字符位置，具体每一段放几个可以通过插板法计算方案。这样的转移看上去是
\(O{(10^{5}})^3\) ,但是如果我们将字符按个数排序后并按照
\(3,1,2,4\)
的顺序插入，因为保证了有两个只有 \(200\) ，所以复杂度为 \(O(1+200^2 + 200^3 + 10^5)\)
的复杂度，最后一次转移强制要求了段数和插入相同字符位置的数量，第三次则是因为第二次转移后有效位置仅有
\(200\) 个。
听说可以做到 \(O(200^2 + 10^5)\)
，但显然我不会。
20220322
ARC137D
题意
给定一个序列 \(a\) ，反复做前缀异或操作，问若干次操作后
\(a_n\) 的值，询问所有 \([1,k]\) 的答案。
思考
考场上一直在考虑分析单纯的 \(01\)
系数，而忽略了系数之间的内在其它联系，事实上，对于反复执行的可加前缀操作，设距离为
\(d\) ，操作次数为 \(k\) ，那么贡献应该为从 \((0,0)\) 走到 \((d,k-1)\)
的方案数。证明比较简单，将原点的贡献转移拆分到横坐标即可。
更严谨的证明可以使用归纳法，记贡献函数为 \(f(x,y)\) ，\(f(n,k) =
f(n-1,k)+f(n,k-1)\) ，那么考虑其组合意义，第一项代表了前 \(n-1\)
项的和，第二项则是自己在上面的步骤中的累计。
那个 \(-1\) 很讨厌，先不管。
用组合数的形式表示答案，即为 \(\tbinom{n+k}{n}\) ,对其应用卢卡斯定理求出
\(\bmod2\) 的结果，发现当且仅当 \(n\&k = 0\) 时有值，那么对于一个固定的
\(n\) ，有值的 \(k\) 一定可以描述为一个 \(s\) 在二进制意义下的子集。
然后对其做一次 \(\text{FMT}\)
变换即可得到结果。
注意处理被忽略的 \(-1\)
20220323
CF1657D
思路
先做乘法转换，这个没啥说的。然后我考虑的是根号分治，先把不在凸包上的扔掉，对于代价大于
\(B\)
的，枚举选的个数，然后尺取法搞定，对于代价小于 \(B\)
的，直接计算。场上过了，赛后被叉。实际上，对于这种整除的题目，我们都可以考虑枚举倍数约数，然后可以直接计算代价为
\([1,C]\)
的最大权值，然后直接在上面二分就行。
CF1647E
思路
不难发现充要条件是每个点向 \(1\)
的边为最小值。然后考虑 \(dp\) ，直接对点
\(dp\)
不太好做，我们发现它是有关大小的，所以考虑按照向 \(1\) 的边权值从小到大 \(dp\) ，每次枚举一段连续的区间，以及填的值转移，转移是一个前缀和乘上一个组合数再乘上一个幂次。
CF1647F
思路：
看上去就非常暴力，对每个限制建点，两种状态，限制和树上的点的状态推出关系连边，然后暴力确定每个限制的状态看是否冲突即可。实际上这就是模拟了
\(\text{2-SAT}\) 。
考虑这个东西为什么和 \(\text{2-SAT}\)
的正常做法一样的，正常做法是找强连通分量，
拓扑排序后对每个点选拓扑序大那个值。和我们的暴力模拟过程没啥区别。
HaltOJ126(2-SAT 的简单理解)
思考：
有一些比较奇怪的限制，然后每个人在每个点就两种状态，要想起一个东西叫
\(\text{2-SAT}\) ，我们令 \(statu[i][j]\) 表示 \(i\) 子树内是否有 \(j\) ，那么很容易构造出标准的 \(\text{2-SAT}\)
限制，然后我们考虑约束，分类讨论一下。以 \(\text{2-SAT}\) 的形式来说，对于 \(x\) 的每个儿子 \(v\) ，两个点都不能同时在 \(v\) 中。同时，如果 \(lca(x,r) \neq x\) ，那么两个人都必须在
\(x\) 子树内。如果 \(lca(x,r) = x\) ，那么 \(a,b\)
只能有一个在子树外，就是一个为假那么另一个为真，除此以外，如果 \(x \neq r\) ，那么 \(a,b\) 不能在 \(x\) 向 \(r\) 的儿子里。
然后跑一个标准的 \(\text{2-SAT}\) 。
\(\text{Tarjan}\) 跑出来的 \(\text{SCC}\) 编号是反拓扑序。
\(\text{2-SAT}\) 的一些限制：强制
\(u\)
为真，那么把假连向真，反之亦然。其它情况下注意逆否命题也要连边
\(\text{2-SAT}\) 图的一些性质：\(u \rightarrow v \Rightarrow \overline{v}
\rightarrow \overline{u}\)
\(\text{2-SAT}\)
合法性：同一变量的两个状态不在同一 \(\text{SCC}\)
内是存在方案的充要条件，必要性显然，充分性用构造法证明。
\(\text{2-SAT}\)
方案构造：依次考虑每个变量，选择 \(\text{SCC}\)
编号较小那个值，那么同一变量不会直接冲突，假设先前的点 \(v\) 推出了 \(\overline{u}\) ，并且 \(\overline{u} \rightarrow
u\) ，因为刚刚提到的性质，一定有 \(u\rightarrow
\overline{v}\) ，我们一定会选拓扑序较大的 \(\overline{v}\) ，因此选择不会冲突。
20220325
CF1656D
题意：
您有一个 \(n\) ，您需要找一个
\(k \in[2,\infty)\) ，使得 \(n\) 可以被表示为 \(k\) 个模 \(k\)
意义下不同的数，多解可以输出任意一个。
多测 \(T\leq
10^5,n\leq10^{18}\)
思考：
因为要找的 \(k\) 个数模 \(k\) 意义下不同，我们又知道任意一个数 \(a\) 都可以表示为 \(a=b \times k +r\) ，所以不妨先把模 \(k\) 的余数和，也就是上式中的 \(r\)
提取出来，我们得到了一个新的式子。下面设 \(n\) 为 \(k\) 个数的和。 \[
n = c\times k + \dfrac{k\times(k+1)}{2}
\] 其中 \(c\) 表示这 \(k\) 个数对应 \(b\)
的和。分母让人很不爽，所以乘过去。至于为什么是 \((k+1)\times k\) ，是为了让 \(c\) 可以取到 \([0,\infty)\) \[
2n = (2c+k+1)\times k
\] \(2n\)
的两个因子奇偶性不同，所以如果我们的 \(n\) 为奇数就可以直接令 \(k=2\) ，否则我们每次令 \(k\) 取 \(2,4,8,\cdots\) ,直到 \(\dfrac{2n}{k}\) 为奇数为止，这个时候记
\(res = \dfrac{2n}{k}\) ，如果 \(res\) 较大，则取对应的 \(k\) ，否则取 \(k=res\) 。
注意特判掉一些边界情况，比如 \(2\)
的次幂，\(2\) 的次幂，还有 \(2\) 的次幂。
参考代码
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 #include <bits/stdc++.h> #define INF 1000000000 #define int long long #define pii pair<int,int> using namespace std;template <typename _type>inline void read (_type &x) x=0 ;int f=1 ;char ch=getchar (); while (ch!=45 &&(ch>'9' ||ch<'0' ))ch=getchar (); if (ch==45 ){f=-1 ,ch=getchar ();} while (ch<='9' &&ch>='0' ){x=x*10 +ch-48 ;ch=getchar ();}x*=f; } template <typename _type>void cmin (_type &a,_type b) min (a,b);}template <typename _type>void cmax (_type &a,_type b) max (a,b);}int i,j,k,n,s,t,m;signed main () read (t); while (t--){ read (n);int ans=-1 ; for (i=2 ;i<1ll <<62 ;i*=2 ){ int res=2 *n/i; if (res%2 ){ if (res>i){ ans=i; break ; } else { ans=res; break ; } } } if (ans==1 )puts ("-1" ); else printf ("%lld\n" ,ans); } return 0 ; }
CF1656E
题意
您有一棵 \(n\)
个点的无向无根树，您需要为每个点安排一个权值 \(a_i\in[-10^5,10^5]\) ，使得删掉任意一个点之后剩下连通块的权值和相同，注意安排的权值不能为
\(0\) 。
多测 \(T\leq 10^4,\sum n \leq
10^5\)
思考
诈骗题。我们考虑指定一个根，就让它是 \(1\) ，然后随便删一个点 \(u\) ，那么 \(u\)
的所有儿子的子树都必须有同一个值，我们可以尝试安排每一棵子树的权值和，这是可以做到的，因为可以让根控制这个值。不妨安排每颗子树的权值和为
\(1\) ， 那么我们再安排整个树的权值和为
\(2\) ，就可以让删掉每个点 \(u\) 后剩下的连通块权值和相同。\(u\) 的所有儿子子树的权值和都为 \(1\) ，而除开 \(u\)
的子树后的那个连通块的权值和就是整棵树的权值和 \(2\) ，减去 \(u\) 子树的权值和，就是 \(1\) ，也和 \(u\) 所有儿子的子树的权值和相同。
但是有一个问题，如果一个点 \(u\)
只有一个儿子，那么 \(u\)
的权值会被安排为 \(0\) ，是不合法的，所以我们需要更改一下安排的方式，对于一个点，设它子树的权值和为
\(x\) ，
并且它所有儿子的子树的权值和均为 \(y\) ，而且整棵树的权值和为 \(x+y\) 。这是合法的必要条件，因为我们需要让
\(a_i \neq0\) ，所以安排根的权值为 \(0\) ，其它点按深度模 \(2\) ，的值安排 \(-1\) 和 \(1\) 即可。
代码
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 #include <bits/stdc++.h> #define INF 1000000000 #define LL long long #define pii pair<int,int> using namespace std;template <typename _type>inline void read (_type &x) x=0 ;int f=1 ;char ch=getchar (); while (ch!=45 &&(ch>'9' ||ch<'0' ))ch=getchar (); if (ch==45 ){f=-1 ,ch=getchar ();} while (ch<='9' &&ch>='0' ){x=x*10 +ch-48 ;ch=getchar ();}x*=f; } template <typename _type>void cmin (_type &a,_type b) min (a,b);}template <typename _type>void cmax (_type &a,_type b) max (a,b);}const int N=1e6 +10 ;int i,j,k,n,s,t,m;vector<int > e[N]; int val[N],fa[N],dep[N],deg[N],tar[N];void dfs (int u) if (u==s)tar[u]=val[u]=0 ; else tar[u]=val[u]=dep[u]%2 ?1 :-1 ; for (int v:e[u]){ if (fa[u]==v)continue ; dep[v]=dep[u]+1 ,fa[v]=u;dfs (v);val[u]-=tar[v]; } } signed main () read (t); while (t--){ read (n);dep[1 ]=1 ;s=1 ; for (i=1 ;i<=n;i++)e[i].clear (),val[i]=0 ,tar[i]=deg[i]=0 ,fa[i]=0 ; for (i=1 ;i<n;i++){ int x,y;read (x),read (y); e[x].push_back (y),e[y].push_back (x); deg[x]++,deg[y]++; } for (i=1 ;i<=n;i++)if (deg[i]>deg[s])s=i; dfs (s); for (i=1 ;i<=n;i++)printf ("%d " ,val[i]); puts ("" ); } return 0 ; }
CF1656F
题意
您有 \(n\)
个点，每个点有一个权值 \(a_i\) ，定义一张有权无向完全图 \(K(t)\) 为每个点 \(i\) 向 \(j\) 连一条权值为 \(a_i\times a_j+(a_i+a_j)\times t\)
的无向边后所构成的图，定义 \(f(t)\) 为
\(K(t)\)
最小生成树的权值和。您需要对所有的实数 \(t\) 求出 \(f(t)\)
的最大值并输出它，如果最大值不收敛，那么输出 INF。
多测，\(T\leq 10^4,\sum n\leq 2\times
10^5,-10^6\leq a_i\leq 10^6\)
思考
场上差那么一点点就 15Ton 了
一个瓶颈在排序的线性做法。
记 \(d_i\) 表示点 \(i\) 的度数。
判断 \(\text{INF}\)
是简单的，只需要看能不能凑出 \(\sum a_i\times
d_i\) 分别为正和负或者 \(0\)
就行，如果凑不出来，令 \(t\)
为正无穷或者负无穷，然后它就不收敛了。
现在已知有解。
考虑固定一个 \(t\) 后怎么快速求
\(\text{MST}\) 。做个恒等变形，权值为
\((a_i+t)\times (a_j+t)-t^2\) ，把 \(t^2\) 给扔掉。
结论是排序后按正负性断开，\(a_1\)
向所有 \(a_i\) 大于 \(0\) 的连边， \(a_n\) 向所有 \(a_i\) 小于 \(0\) 的连边，\(0\) 无所谓。
证明可以考虑 Prime 算法的过程，最开始一定是 \(a_1\) 到 \(a_n\) 。然后后面不会取到正负性相同的，并且一个点一定是连向
\(a_1\) 或者 \(a_n\) 。
如果处理一个前缀和，知道正负交界的位置之后可以快速算，从小到大枚举
\(t\) ，然后双指针维护交界处。
可以证明 \(t\) 一定取到每个 \(-a_i\) 。如果夹在两坨中间，那么由于具体选哪些边是固定的，根据
\(\sum a_i\times d_i\)
正负性调整即可。
不会取到 \([a_1,a_n]\)
外面去，因为我们已经判了无解，所以取到边界外面时 \(\sum a_i\times d_i\)
的正负性会导致向里面调整更优。
20220329
HaltOJ129(Powerful Number 筛)
思考:
打个表发现 \(f\) 是积性函数。
然后 \(f(p^c)\)
是好求的，考虑亚线性筛法。
我也不知道为啥会想到 PN 筛，总之这种东西各种筛法都可以尝试一下。
PN
筛和其它亚线性筛法一样，是用来求一些积性函数的前缀和的，它的关键在于构造一个好求的前缀和的
\(g\) ，满足 \(g(p)=f(p)\) ，然后构造一个 \(h\) ，满足 \(f=h
* g\) ，乘法为迪利克雷卷积。
这里我们构造 \(g(x)=1\)
积性函数有个性质，\(f(1)=1\) ，所以展开下 \(f\) ，发现 \(f(p)=1=h(1) * g(p)+h(p) * g(1)\) ，然后
\(h(p)=0\) ，由于 \(h\)
也是个积性函数（迪利克雷卷积的性质），所以 \(h\) 只会在 PN 处有取值，PN
的定义为每个质因子次数都大于等于 \(2\)
的数。
可以证明所有比 \(n\) 小的 PN 个数是
\(O(\sqrt n)\) 的 。
可以预处理 \(\sqrt n\)
以内的所有质数，然后枚举指数得到每个 PN，这个 \(dfs\) 的过程中可以记录一下对应的 \(h\) ，\(h\)
的转移是好做的，因为只需要求 \(h(p^c)\) 。
这里不难发现 \(h(p^c)=f(p^c)-f(p^{c-1})\) 。
原因是 \(g\) 实际上是 \(1\) ，而 \(f / 1 =
f * \mu\)
20220331
思考
限制不好弄，考虑转化限制，不难发现，如果建图，并依次加入有向边，那么任意一个时刻，都需要满足当前图及其补图都是一个传递闭包，即，如果能间接
\(a\rightarrow b\) ，那么 \(a,b\) 有边。这样的图不是很多，是 \(n!\) 个的，只需要考虑图之间的转移就行。
这样的图和一个 \(n\)
的排列一一对应，构造方案为如果 \(a,b\)
为逆序对，那么加入一条边 \((a,b)\) 。加入一条边时，只需要枚举相邻的逆序对并交换，转移可以康托展开得到交换后的编号。限制也比较好做，转移的时候看看强制在前面的边在不在里面就行。
复杂度为 \(O(n!\times n \times
(n+m))\) ，常数较小，可以过。
20220402
思考
对于这种翻转的博弈问题，其实都可以做一个转化：不要翻转颜色，而是在每个翻转的地方再放一个棋子，这样不会改变游戏的胜负性，因为如果原处没有棋子，那么等效，如果有棋子，那么有两个，在
\(SG\)
的意义下，这是可以抵消的。如果以组合方式理解，那么因为放了之后如果有人操作了，那么另一个人把它的操作复制一遍即可，由于两个人都是最优操作，所以可以抵消。
有了这个转化，每个棋子都变成了一个独立的游戏，该局面的 \(SG\)
值就不难计算了，按照定义计算出每个位置的 \(SG\) 值然后异或查表即可。
思考
场上写了个 \(O(n^3)\)
卡常卡过去了，实际上 \(O(n^2)\)
的有点难想，它是把构造表达式的过程视作了一个添加左右括号的过程，总之非常神仙。
有个对于区间 \(dp\)
的常数优化思路，可以改变一下枚举顺序，让数组访问尽量连续，以便最大程度利用好
\(L1\) ，可以节省大量内存操作时间。
咕一篇常数优化文章。