做题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$ 的次幂。

参考代码

#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$ 即可。

代码

#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$，可以节省大量内存操作时间。

咕一篇常数优化文章。