danihao123's Blog

给定正整数$n, m$，求$\sum_{i = 1}^n\sum_{j = 1}^m \varphi(ij)$，膜$10^9+7$输出。

$n\leq 10^5, m\leq 10^9$。

给定$n$，分别求出$\mu(x^2)$和$\varphi(x^2)$的前$n$项和。

$1\leq n\leq 10^9$。

只会做水题力……qwq（搞错大小写，自裁请）

每条边存在的时间事一个区间，因此考虑线段树分治……首先当然要写一个可撤销并查集。

然后每个点维护他到父亲的边的边权膜2，合并啥的和食物链就很类似力……然后判定已联通两点间边数的奇偶性就直接把两个点到根的值加起来就行了，因为LCA到根的部分会算两遍，对答案无影响。

代码：

APIO的时候听了一下wqs二分，做了这题，然后现在才写题解……

wqs二分的思路大抵就是你要求必须选$k$个，那就二分每个操作的一个“额外代价”，然后进行没有限制的选择。然后最后选出来的个数事和你二分的代价正相关/反相关的。

这道题的话，就二分选择黑边的代价，然后跑一般的最小生成树（有相同边权时要选择黑边！）。当然我们会遇到一个问题，就是二分到$x$的时候选的比$k$多，到$x + 1$的时候又比$k$少了。这道题的处理方法，事考虑代价为$x$时，其实存在选$k$个的最优解（如果说大于$x$那就没了），因此我们钦点代价为$x$跑一遍限制只能选$k$条黑边的最短路即可。

代码：

肉肉肉肉，，，

碰置换群啥的不是第一次了……这个题就是给你一堆置换（不要忘记还有一个幺元啊），然后限制颜色数量，求本质不同解个数。那么考虑使用Burnside引理，接下来考虑怎么计算每个置换的不动点数量，这个要求每个循环的颜色一致（不就事Polya定理了吗），所以说可以用背包DP搞一搞。

代码：

逆矩阵文明，，，

很显然我们可以定义一个状态$f[i][j]$表示当前血量为$i$走到$j$的概率，然后肥肠爆歉这个东西没法DP（可能会有的点的伤害为0，这样可以凿出来环）。考虑高消，这个东西有个好处是不可能从血量低的到血量高的状态，所以可以从大到小枚举血量，这样各层事独立的，复杂度比直接高消降低了很少。可惜复杂度为$O(sn^3)$（设血量为$s$），会T掉。

考虑转移的过程，转移时等价于解这样一个方程：

$$\begin{aligned} a_{11}x_{1} + a_{12}x_{2} + \ldots + a_{1n}x_{n} &= c_1\\ a_{21}x_{1} + a_{22}x_{2} + \ldots + a_{2n}x_{n} &= c_2\\ &\ldots\\ a_{n1}x_{1} + a_{n2}x_{2} + \ldots + a_{nn}x_{n} &= c_n \end{aligned}$$

其中的未知数$x$事我们要求的东西，$c$表示从高血量状态转移过来的概率（这个可以视作常数）。根据友矩阵那一套理论，这一系列方程等价于以下等式：

$$\begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \ldots & a_{nn} \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2} \\ \vdots \\ x_{n} \end{bmatrix} = \begin{bmatrix} c_1\\ c_2\\ \vdots\\ c_n \end{bmatrix}$$

不妨将之简记为$AB = C$，其中我们只有$B$不知道，要求的也是$B$。我们除一下就可以得到$B = A^{-1}C$，然后我们还发现每一层的$A$都是一样的，所以每一层的$A^{-1}$也都是一样的，预处理即可。这样转移部分的复杂度就变成了$O(sn^2)$（矩阵乘法在这里事方阵乘列向量）。

至于逆矩阵的求法，我们知道对矩阵做初等变化也就等价于乘上另一个矩阵。因此，我们将一个矩阵$A$用类似于高消的手段消为单位阵$I$，所做的初等变换也就等价于乘上$A^{-1}$。我们对一个单位阵$I$作用上一样的操作，也就等于给这个单位阵乘上了$A^{-1}$，这样我们就得到了$A^{-1}$。

代码：

后几页有我会做的题……很好，我很安详，，，

考虑将所有数质因数分解。那么询问$[l, r]$中所有数的积是否是$d$的倍数的本质就是对于$d$的每一类质因子，询问区间中该类质因子的指数之和是否不小于$d$中的。

考虑到数的范围都很小（不超过100000），我们可以先线性筛预处理，这样一次分解质因数的复杂度就降为了$O(\log n)$。至于维护区间每类质因子的指数和这种事……就用主席树处理吧。

代码：

老早做的题……

一看单调不降就想去用差分……但差分不好推（比下面的颓法要多一步……）。其实我们发现，只要给$[L, R]$里每种整数分配出现次数，原序列就可以唯一确定了。

因此我们把$[L, R]$中每个整数的出现次数当做一个变量，他们加起来应该等于一个$[1, n]$中的整数。用隔板法很容易退出来式子是（令$l = R - L + 1$）：

$$\sum_{i = 1}^n \binom{i + l - 1}{l - 1}$$

看起来玩不动了……但是我们给式子加上一个$\binom{l}{l}$（其实就是1），然后我们会发现式子可以用杨辉三角的递推式合并成一个组合数，即$\binom{n + l}{l}$。然后求这个组合数还需要Lucas定理……

代码：

本来想做JZPKIL的……但卡常太恶心了

上来先颓式子：

$$\DeclareMathOperator{\id}{id} \begin{aligned} f_d(n) &= \sum_{i = 1}^n [(i, n) = 1]i^d\\ &= \sum_{i = 1}^n i^d\sum_{k | n, k | i}\mu(k)\\ &= \sum_{k | n}\mu(k)\sum_{i = 1}^{\frac{n}{k}} (ik)^d\\ &= \sum_{k | n}\mu(k)k^d h_d(\frac{n}{d})\\ &= ((\mu\cdot\id^k)\ast h_d) \end{aligned}$$

其中$h_d$表示指数为$d$时的等幂求和函数。然后我们可能会想，如果这个函数是积性函数，那么我们可以对质因数分解的每一种质因数都求一遍答案，而由于$\mu$的存在（对于质数的幂$p^k$的因数，只有$1$和$p$的莫比乌斯函数值不为0），所以需要处理的情况只有两种。

不过很可惜，$h_d$显然不是积性函数，所以最后的整个卷积也不是积性函数。但是我们注意到$h_d$事一个$d + 1$次多项式，所以我们可以把多项式每一项都当成单独的函数，然后每个单独函数卷出来都是一个积性函数。至于求多项式每一项的系数，用伯努利数即可。

代码：

物理题可还行（其实我是想学势能方法，然后误入了……）

给每个星星（假设他在的位置是$(i, j)$）定义势能$E_p = i^2 + j^2$，定义势函数$\Phi(S)$来表示状态$S$时所有星星势能的和。

然后我们发现，当两个星星互相吸引时（假设他们同行，坐标分别为$(i, j)$和$(i, k)$，且$j<k$），他们的坐标会变为$(i, j + 1)$和$(i, k - 1)$，势能的总减少量（也就是势函数的减小量）为$2(k - j - 1)$。

因此，整个过程中势函数的总减小量，就是答案的两倍。因此算出操作前后的势能做差即可……

代码：