做题2

发表于 更新于 分类于

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){a=min(a,b);}
template<typename _type>void cmax(_type &a,_type b){a=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){a=min(a,b);}
template<typename _type>void cmax(_type &a,_type b){a=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

20220330考试T2

思考

限制不好弄，考虑转化限制，不难发现，如果建图，并依次加入有向边，那么任意一个时刻，都需要满足当前图及其补图都是一个传递闭包，即，如果能间接 \(a\rightarrow b\) ，那么 \(a,b\) 有边。这样的图不是很多，是 \(n!\) 个的，只需要考虑图之间的转移就行。

这样的图和一个 \(n\) 的排列一一对应，构造方案为如果 \(a,b\) 为逆序对，那么加入一条边 \((a,b)\)。加入一条边时，只需要枚举相邻的逆序对并交换，转移可以康托展开得到交换后的编号。限制也比较好做，转移的时候看看强制在前面的边在不在里面就行。

复杂度为 \(O(n!\times n \times (n+m))\)，常数较小，可以过。

20220402

20220401考试T1

思考

对于这种翻转的博弈问题，其实都可以做一个转化：不要翻转颜色，而是在每个翻转的地方再放一个棋子，这样不会改变游戏的胜负性，因为如果原处没有棋子，那么等效，如果有棋子，那么有两个，在 \(SG\) 的意义下，这是可以抵消的。如果以组合方式理解，那么因为放了之后如果有人操作了，那么另一个人把它的操作复制一遍即可，由于两个人都是最优操作，所以可以抵消。

有了这个转化，每个棋子都变成了一个独立的游戏，该局面的 \(SG\) 值就不难计算了，按照定义计算出每个位置的 \(SG\) 值然后异或查表即可。

20220401考试T3

思考

场上写了个 \(O(n^3)\) 卡常卡过去了，实际上 \(O(n^2)\) 的有点难想，它是把构造表达式的过程视作了一个添加左右括号的过程，总之非常神仙。

有个对于区间 \(dp\) 的常数优化思路，可以改变一下枚举顺序，让数组访问尽量连续，以便最大程度利用好 \(L1\)，可以节省大量内存操作时间。

咕一篇常数优化文章。