Prutekoi's blog

这波啊......

day1考场全程降智，不知道在想啥。。。

d1t1

这题想了个垃圾做法，还是别说了，说出来丢人。。。
写了个垃圾平衡树，写得天昏地暗。。。
后来发现挂了，还以为是写挂了，其实就是做法挂了。。。
还是log^2的。。。

正解是线段树或者树状数组二分。注意到答案就是 $\max\{\min(a_i,b_i)\}$，其中 $a_i$ 是非严格单调递增，$b_i$ 是非严格单调递减。那么当取到一个位置 $i$ 时，我们比较一下 $a_i$ 和 $b_i$ 的大小就可以知道往哪里走了。（而不是去比较答案，因为它是非严格单调的。。）还有一个稍微麻烦一点的地方在于要求答案最大的时候位置最大。这个也随便弄一下就行了。虽然它看起来很卡常，但CCF神机，基本上写了什么垃圾都能跑过。

d1t2

这题因为考前复习看了这玩意，所以考场完全被带偏了（它们的差别在于组合数，乘了组合数之后就发生质变了。。）。开场看完题之后看到这个东西就觉得我会推，然后推好久无果就去做T1了，做完T1心态已经将近爆炸了（在写得天昏地暗的时候甚至在想退役生活了。），于是后来虽然想到了斯特林数也没时间没脑子推出来了。本来打了 $40$ 分裸暴力，但是考完才发现两部分没分开，导致第二个部分输入 $10^9$ 的 $n$ 时我还在 $O(n^2)$ 求组合数就RE了。。只有 $15$ 分。

考试最后倒是推出来一个东西，但是我要算组合数，发现不会算，就放弃了。下来看看其实还是挺好算的。
主要就是考虑 $m$ 比较小，肯定还是关于 $m$ 的暴力。组合数就是 $\frac{n^{\underline m}}{m}$，我们就把 $m!$ 分解之后去除上面的数就行了。总复杂度大概是 $m\log\log m$ 的。

int C(int n,int m){
	for(int i=0;i<m;i++)d[i]=n-i;
	for(int i=2;i<=m;i++){
		if(vis[i])continue;
		int cnt=0;
		for(int j=i;j<=m;j*=i)cnt+=m/j;
		for(int j=n/i*i;cnt;j-=i){//这里复杂度是mloglogm
			while(d[n-j]%i==0&&cnt)
				d[n-j]/=i,cnt--;//因为cnt总和是m/logm的，所以这里复杂度是m/logm
		}
	}
	int ret=1;
	for(int i=0;i<m;i++)ret=1ll*ret*d[i]%mod;
	return ret;
}

正解就是用斯特林数转一下下降幂。主要想法是因为组合数是阶乘形式，就会想要再凑一个阶乘形式来消掉一些东西，而下降幂正好也是阶乘形式。
这玩意推式子的思路是原题
有趣的是后来看到了这道题：
然后期望显然是 $1$，方差我熟练地应用 $V(x)=E(x^2)-E(x)^2$，二项式反演推出一个式子之后发现恰好就是这个题形式的式子，然后就很轻松地变形 $x^2=x(x-1)+x$，最后得到方差也是 $1$。

d1t3

啊，这题是论文题，考场打了15分暴力。这档分是裸的拟阵贪心，其他的分我大概也不会吧。。

Orz dky考场想到了做法OrzOrz，不过最后他还是敲了暴力，口胡AC Orz

保序回归，主要想法是把这些元素之间的偏序关系先找出来（类比最小生成树，对于最小生成树来说非树边要比它覆盖的树边不小。而线性基就是一个元素要比线性基中能异或出它的集合都不小。）
然后通过一通分析之后发现可以整体二分，每次二分的决策可以转化为一个取值为 $01$ 的问题，于是就变成了最大权闭合子图。我是把论文看了一遍了。。。然而它并不是所有地方都有用，基本上精华在这篇题解了。

这题的暴力分也值得说一说。
前 $15$ 分可以直接爆搜之后贪心判断是否合法，是最裸的暴力。

后面的分数就需要看出偏序关系，就是说对于最小基之外的数权值必须比能异或出它的集合都不小，大也类似。这个类比生成树即可。

接下来 $15$ 分基很小，我们可以只搜AB里的数，然后其他的数就根据偏序关系找最优即可。

接下来 $20$ 分的权值只有两种，那么就可以套用上面提到的最大权闭合子图。

而这 $50$ 分的权值范围都很小，可以做关于权值的暴力，发现它就是切糕，直接套这个做法就可以获得 $50$ 分。
而切糕这题的做法我的理解就是“二元关系”，只不过每个变量可以有很多取值，限制关系是对于一个变量取值的前缀和另一个变量取值的后缀之间的关系。（这题就是说如果限制 $v_i\leq v_j$，那么对于每个 $k$，若 $v_i>k$ 则 $v_j$ 不能 $\leq k$，连 $inf$ 边限制）特别地，对于第三档暴力这个做法和最大权闭合子图等价。

最后 $10$ 分暴力是A与B相同。那么当我们得到偏序关系之后会发现它们都是 $=$。我们在相等的变量之间连边，那么对于每个联通块的值都应该一样，这样就是求一个 $x$ 使 $\sum(x-v_i)^2$ 最小。直接二次函数最值即可。

现在才发现这个暴力分都这么好拿QAQ，哎考场失智是传统艺能

d2t1

这题考场想出了 $O(n2^n)$ 时间 $O(2^n)$ 空间的做法，然而很多人的空间复杂度多个 $n$，导致只能放弃 $20$ 分，出来骂出题人卡空间。。我觉得干得挺漂亮的啊

主要想法是发现状压很显然，但是裸做是 $O(n^22^n)$ 的，瓶颈在于每次贡献的计算。然后很自然地发现贡献每次改变的东西并不多，每次贡献变化的部分只在某一位变化时变化。然后我们如果每次在上次的贡献上面修改的话可以做到 $O(n\cdot\sum popcount(i\oplus(i-1)))$，随便等比数列求和分析一下发现这玩意其实是 $O(n2^n)$ 的。很多人的做法是 $i$ 的贡献从 $i-lowbit(i)$ 的贡献转移过来，这样只改一位，时间复杂度显然非常对，但是这就导致了他们需要记集合，空间复杂度爆炸。

d2t2

这题考场降智，想出个寂寞。。最后敲完T3暴力之后回来看才想到了一个线段树合并的垃圾做法。但是当时看起来时间相当不够，于是放弃了这个做法只敲了裸暴力和链的做法（树状数组）30分。现在看来这个选择非常正确，因为线段树合并空间根本不够。。。loj只过了 $40$ 分。

这题做法其实有很多。

首先我们需要变一下形。。$v_y+d(x,y)=v_y+d_y-d_x$，然后我们维护 $v_y+d_y$，在统计贡献时考虑偏移量就行了。。

可以按位考虑。如果我们关心 $2^i$ 这一位，那么我们可以先把所有数对 $2^{i+1}$ 取模（因为不管加法和异或都与更高的位没有关系），然后发现这一位是 $1$ 的所有值构成了一个区间。这样就可以有线段树合并的做法了。而如果是一条链的话就无须合并，直接写树状数组就行了（考场想到的垃圾做法）这个想法是之前做过的一道CF题里面出现的，但是当时我就不会，大家都会/dk $O(n\log^2 n)$
当然，这个做法如果我们不写线段树合并也可以套上dsu on tree，不过复杂度就高达 $O(n\log^3 n)$..（不过竟然有人说这个按位+dsu+树状数组过了！！！震撼我马）

还可以考虑另一种思路：当我们从一个点的所有儿子转移到它自己时，相当于是子树内所有值都 $+1$。那么我们考虑 $+1$ 会造成什么影响。。对于第 $i$ 位，如果 $x\mod 2^i=2^i-1$，那么 $x+1$ 会异或上 $2^i$。发现了这么一种思路，现在我们关心的只是一个位置的值的个数，那么开桶即可。然后套上dsu即可做到 $O(n\log^2 n)$。线段树合并也可以，虽然去掉了dsu的 $\log$，但是从桶强行套上个线段树的话仍然会多个 $\log$，仍然是 $O(n\log^2n)$ 的做法。z7z，skyh都是写的这个做法，但是z7z空间开小了，只拿了 $80$。

上面的这种思路还可以优化，即我们发现它的贡献是可减的，那么套上天天爱跑步的trick即可做到 $O(n\log n)$。还有一种树上差分的做法，优化优化之后也变成了这个做法，只不过解释不太一样...cold_chair写的是“树上差分”的做法...然后我们也可以发现我的那个垃圾做法还可以抢救一下，因为它也是可减的，可以做到 $O(n\log^2n)$，空间复杂度也可以接受了。

还有一种trie树的做法：考虑一个数 $+1$ 时是把末尾连续的 $1$ 都变成 $0$，再把最后面的 $0$ 变成 $1$。那么我们把数建出01trie，不过它是从低位往高位插的。这样我们就可以 $O(n\log n)$ 实现整体 $+1$ 操作：交换相应的左儿子和右儿子即可。这样我们再写一个trie树合并即可 $O(n\log n)$。这是一道Ynoi的trick。硬核数据结构大王zbh写了这个做法。

d2t3

这题暴力分大放送...70分...
上来先推了反演，但是发现复杂度太高，就老老实实一个一个敲暴力去了，而且敲得效率极其低下，导致没时间写t2了...
草，现在发现直接那个 $O(n^5d)$ 暴力在loj就能A掉，在luogu也75分。（这个只是因为出题人没有卡，其实直接来一个所有边权相同且约数个数最大就能卡掉了。然而skyh强强加上了边集哈希记忆化，就很难卡很难卡了）

首先反演一波以后就变成了对于每个 $d$，把边权是 $d$ 倍数的边拿出来，求出它们构成的生成树的边权和的和。我们知道矩阵树可以求生成树边权积的和，形式不太一样。那么暴力就是考虑每条边的贡献，看它在生成树中出现多少次再乘边权。然而这个东西其实是可以一遍矩阵树 $O(n^3)$ 做的。

这里的想法是 因为他是和的和，我们能求积的和。那么我们想办法要把和转化成积。一个很自然的思路是用指数函数，$a^xa^y=a^{x+y}$。但是我们还需要求和...指数的指标是不能求和的啊...那么要再让它“下来”，这时就要用到泰勒展开：$e^x=\sum\frac{x^i}{i!}$，这样就做到了让指标“下来”。于是做法就呼之欲出：原边权为 $v$ 的边有新边权 $e^{vx}$，这样跑完矩阵树之后再取一次项系数即可。具体实现是把边权表示为 $a+bx$，然后做 $\mod x^2$ 的乘法。

这里用组合意义和EGF来思考会更加简单。（这是八十中集训的课件QAQ）

这里还要注意一下如果没有常数项是不能求逆的。但是我们仍然可以不多 $\log$：我们只要每次把最低项最小的行换上来，即可把其他的行都消完了。（$\frac{x^cf}{x^cg}=\frac{f}{g}$）
而如果我们每次直接求逆的话，可以被生成树数量模意义为 $0$ 的图卡掉。（关注常数项的话发现它就是跑了求生成树数量的矩阵树）构造方法
这个思路有个原题。。。

还有一个做法是我们考虑要求每条边的贡献的话，强制经过一条边相当于把这条边的两个点合并了，然后再跑矩阵树，因为矩阵树还要删去一行一列，所以我们可以看作它就删去了这两行两列。（即经过强制 $(i,j)$ 的生成树数量为删去 $i,j$ 行 $i,j$ 列的矩阵的行列式。）然后我们可以用什么代数余子矩阵来求一下啊。。。（代数余子矩阵是伴随矩阵的转置，伴随矩阵是 $|A|A^{-1}$，于是可以 $O(n^3)$ 求）
然而我现在还是不懂它是怎么求的。。（我只会求强制经过 $(i,n)$ 的，即跑出前 $n-1$ 行 $n-1$ 列的代数余子矩阵即可）代码

果然自己闷头研究是研究不出啥的。。后来U群里有人问了相似问题之后EI发了资料

发现我们一次只能求出前 $n-1$ 行 $n-1$ 列的伴随矩阵，那么我们还是考虑只用这些信息来求强制经过 $(i,j),i,j\not = n$ 的方案数。我们把无向边看作两条有向边，那么就变成了强制经过某条有向边的以 $n$ 为根内向生成树的问题，那么如果强制经过 $j\to i$，可以强制 $i$ 为 $j$ 的父亲，这样就是把 $j$ 的出边除了 $j\to i$ 都删去即可。也就是把基尔霍夫矩阵中这一行只把 $a_{jj}=1,a_{ji}=-1$，其他都为 $0$。（因为对角是出度），然后计算行列式就直接在这一行中拉普拉斯展开即得 $A_{jj}-A_{ji}$..然后因为是无向边所以还要计算一次 $i\to j$。。在无向图中它们的差别就在于以 $n$ 为根时生成树中谁是谁父亲。

那么现在只需求出伴随矩阵。我们知道有这样的关系：$AA^*=|A|\cdot I_n$。那么如果矩阵的秩为 $n$，我们就可以直接求行列式和逆来得到伴随矩阵。如果矩阵秩 $\leq n-2$，那么因为任意余子式都为 $0$，所以伴随矩阵为 $O$。

如果矩阵秩为 $n-1$，意味着存在不全为 $0$ 的实数 $q_1,q_2,...,q_n$ 满足 $\sum\limits_{i=1}^nq_ic_i=0$，其中 $c_i$ 是列向量。
（注意nealchen写的是全不为 $0$，他推的大概是基尔霍夫矩阵，这是特例满足任意 $n-1$ 个线性无关，但实际上一般矩阵不一定存在全不为 $0$ 的。）
经过一番推导我们发现这些代数余子式是成比例的！具体地，对于每一行 $r$，$\frac{A_{r1}}{q_1}=\frac{A_{r2}}{q_2}=...=\frac{A_{rn}}{q_n}$（注意到如果 $q_i=0$，那么 $A_{ri}$ 一定也是 $0$，因为 $q_i=0$ 说明其他列之间线性相关，那么余子式一定是 $0$。）
对于行这一结论也成立。那么现在只要得到比例系数和某一项即可得到所有的代数余子式。求解比例系数依据定义就是一个 $n$ 元 $n$ 个方程的线性方程组，而一个代数余子式直接消元即可，那么我们就可以在 $O(n^3)$ 求出所有代数余子式，得到伴随矩阵（转置得到伴随矩阵）！

最近看了3b1b的视频，又注意到一个有趣的结论，来写一下吧。

$|A^*|=|A|^{n-1}$

由上面的推导我们已经得到了当 $|A|=0$ 时 $A^*$ 的各行各列成比例，显然 $|A^*|=0$。
当 $|A|\not =0$ 时，$A^*=|A|A^{-1},|A^*|=||A|A^{-1}|=||A|IA^{-1}|$
我们由矩阵的几何意义（向量空间的线性变换）和行列式的几何意义（变换前后面积的比值）可以显然得到
$|AB|=|A||B|,|A^{-1}|=|A|^{-1}$，而 $||A|I|=|A|^n$，故 $|A^*|=|A|^{n-1}$ 得证。