题意：对于任意 $n$ 个 $[1,D]$ 的数，求其中能找出 $m$ 对相同的数的方案数量。 首先，特判掉 $2m \le n - D$ , $2m > n$ 的情况，明显答案分别是 $D^n,0$。 稍微推下式子，不难发现题设条件即为出现次数为奇数的数个数不超过 $n-2m$ 的方案数量。 我们假设钦定 $i$ 个数字出现次数是奇数的方案数量是 $g_i$ ，恰好有 $i$ 个数被出现次数为奇数的方案数量是 $f_i$ ，那么由二项式反演我们有 g_i = \sum_{j \le i ...

4.29 模拟赛A 参见 JOI Open 2016 摩天大楼 B 小W玩游戏这个操作了 $q$ 次后，等价于选 $q$ 行 $q$ 列分别 $+1$ ，使得最后有不超过 $k$ 个奇数。 把行列分开讨论。考虑把 $q$ 次操作写成一个序列，每个数大小在 $1\sim n$ 。我们假设钦定 $i$ 个数字被操作了奇数次的方案数量是 $g_i$ ，恰好有 $i$ 个数被操作了奇数次的方案数量是 $f_i$ ，那么由二项式反演我们有 g_i = \sum_{j \le i} f_i\binom i ...

A 钩子我们按照 $d$ 来分层。如果当前区间长度为 $x$ ，如果它是偶数，挂一个后会变成 $\frac{x}{2}-1$ 和 $\frac{x}{2}$ ，否则会变成两个 $\frac{x-1}{2}$。就这样分层下去，最终得到的必然是 $\log$ 层。 明显每层会有一定数量的人来选，所以我们考虑对每层分别 $dp$ 。每一层明显只会有两种权值，并且我们可以知道每种权值的个数。我们考虑当前如果已经有 $i+j$ 个人选择了位置，其中有 $j$ 个人选的是奇数的块（也就是固定挂中间），$i$ ...

考虑给 $T$ 建一个广义后缀自动机。我们考虑给 $T[i]$ 的所有节点全部打上 $i$ 的标记后，考虑一次询问，我们可以先倍增确定 $s[p_l\dots p_r]$ 所在的节点 $u$ ，于是就是求 $u$ 子树内出现次数最多的标记是谁。 考虑每个点开个动态开点线段树，给 $T[i]$ 所在的节点把 $i$ 这个位置加一，离线询问，然后直接 dfs 的时候线段树合并，在每个点上询问区间内最大值即可。 123456789101112131415161718192021222324252627 ...

A 未来注意树是按照 prufer 序随机生成的，因此树高期望为 $\sqrt n$ ，我们考虑对于每个点，计算它的所有祖先对它的贡献。 比如设当前考虑的点为 $u$ ，其祖先为 $v_1$ ，考虑设祖先到这个点的路径是 $v_1,v_2\dots v_k,u$ ，我们知道 $u$ 的贡献只和这个路径的点在排列中的相对顺序有关。那么怎么计算 $v_1$ 对 $u$ 的贡献？ 我们不妨暂时将这条链重新编号，看成 $1,2,\dots k$ ，我们要统计所有排列下 $1$ 对最后的 $u$ 点的贡献 ...

考虑 dp ，设 $dp[u]$ 表示覆盖完 $u$ 向上的边所需要的最小代价。这个怎么转移呢？ 我们考虑当前 dfs 到了 $u$ 这个点，维护所有包含 $u$ 这个点的路径在钦定被选择时，覆盖完整个 $u$ 的子树所需要的最小代价。如果维护了这个，答案就是所有在 $u$ 子树内起始的路径的最小值。我们考虑用线段树维护 子树内起始的，包含这个点的最小值 这个东西。对于从这个点离开的路径，将它的这个代价设为 $\infin$ 即可。 设 $S = \sum_{v\in son[u]} dp[v] ...

考虑把每一列当成一个不超过 $2^{n}$ 之内的数，于是进行完行的修改后相当于是每个数 xor 上了一个值 $x$ ，于是我们写成式子，这种情况答案就是 \sum_{i=1}^m \min\{popcount(a_i\ xor \ x),n-popcount(a_i\ xor\ x)\}我们可以设 f(x) = \min\{popcount(x),n-popcount(x)\}于是枚举 xor 出来的值 \sum_{a_i\ xor\ x = t} f(t)稍微移下项 \sum_{a ...

我们记 “恰好有 $k$ 次非平局” 的方案数是 $g(k)$ ，“钦定有 $k$ 次非平局” 的方案数是 $f(k)$ 。发现这是一个二项式反演的形式，由二项式反演有公式：（不会可以百度） f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i)所以我们只要求出 $f(k)$ 就做完了这个题。我们可以 dp 求出 $f$ ，设 $dp[u ...

一个看起来挺经典的题。 n\le 40 , m\le 10^5 我们可以先考虑只有两种颜色的情况。比如只有 Red and Blue。 我们设红边权值为 $1$ ，蓝边权值为 $x$ ，那么我们可以写出一个生成函数 $F(x)$ ，并且可以设 $x^i$ 的系数是选择正好 $i$ 条蓝色边的方案数量，也就是选择正好 $i$ 条边的答案。 只要求出这个多项式的系数就好了。于是我们可以考虑对 $F(x)$ 在 $0\dots n$ 插值，插出 $n+1$ 个点值拉格朗日插值即可。插值的过程其实就 ...

开始把 Ax 理解成了可以走任意A的倍数 首先，假设我们想从 $(0,0)$ 到达某个点 $(X,Y)$ ，第一种操作用了 $a$ 次，第二种用了 $b$ 次，那么有 Axa+Bxb = X\\Aya+Byb = Y由 zzh 胎教时期就会的数学知识，我们知道 $a,b$ 可以被解出来。 如果没有障碍点，我们就做完了，显然你只需要做个可重排列就完事了。 然后考虑，现在我们可以把第一种操作看成 $x+1$，第二种操作看成 $y+1$。 现在考虑障碍点这个问题。我们考虑枚举第一个经过的障碍点是谁。 ...

这题其实是上次模拟赛 A 的弱化版。 （下面式子的 $=$ 都指膜 $10^9+9$ 意义下的同余） 我们考虑 $5$ 在 $\mod 10^9+9$ 的时候是有二次剩余的，所以看到通项公式： \frac{1}{\sqrt 5}\left((\frac{\sqrt 5+1}{2})^n - (\frac{\sqrt 5-1}{2})^n\right) = x我们考虑设 $a = \frac{\sqrt 5+1}{2}$ ，那么有 a^n - (-\frac{1}{a})^n = (2a-1) ...

考虑 $dp[i][j]$ 表示结束前 Petya 在 $i$ ，Vesya 在 $j$ 的概率。 那么很明显这东西是不能 dp 转移的。但是我们可以列很多个方程 dp[i][j] = p_j\sum_{v \in E(i)} \frac{1-p_v}{deg_v} dp[v][j] + p_i\sum_{u \in E(j)} \frac{1-p_u}{deg_u} + \sum_{v \in E(i)}\sum_{u \in E(j)} \frac{(1-p_v)(1-p_u)}{deg_ ...

考虑二分，然后变成判断 $\le x$ 的无平方因子数的个数。 我们考虑一个有问题的做法，枚举质数 $p$ ，将 $p^2$ 的倍数全部去掉。不难发现，这样有些数字被去了很多遍。能不能容斥呢？我们考虑枚举无平方因子数 $t$ ，将 $t^2$ 的倍数全部去掉 / 加回来就好了。系数是 $(-1)^c$ 其中 $c$ 为质因数个数。然后可以发现，这个系数就是 $\mu$ 。。 1234567891011121314151617181920212223242526272829303132333435 ...

BSGS 模版题 \begin{aligned}ax_i+bz&\equiv x_{i+1} \pmod p\\a(x_i+\lambda) &\equiv (x_{i+1}+\lambda) \pmod p\\\lambda a-\lambda &\equiv b \pmod p\\\lambda& \equiv \frac b {a-1} \pmod p\\f_i &= x_i + \lambda\\f_x &\equiv a^{x-1}f_1\pmod p\end{aligned}直接 ...

给定一张 $s$ 个点的图，存在 $s-n$ 个边，使得图中形成了 $n$ 个联通块，第 $i$ 个联通块内部有 $a_i$ 个点。 我们现在要再连 $n-1$ 个边，使得该图成为一个树。对于某一种连边方式，我们设原题第 $i$ 个联通块连出了 $d_i$ 条边，那么当前树的权值为 val(T) = \left(\prod_{i=1}^n d_i^m\right) \left(\sum_{i=1}^n d_i^m\right)求所有生成树的权值和。 n \le 3\times 10^4 , ...

基础定义斯特林树分成两类， 第一类：将 $n$ 个元素划分成 $m$ 个圆排列的方案数量。计做 $\left[\begin{array}{l} n \\ m \end{array}\right]$ \left[\begin{array}{l} n \\ m \end{array}\right]=\left[\begin{array}{l} n-1 \\ m-1 \end{array}\right]+(n-1)\left[\begin{array}{c} ...

好的现在开始番剧介绍(bushi 我们先来考虑一个前置问题。假设有 $n$ 种球，第 $i$ 种球有 $a_i$ 个，你需要放在序列上，满足相邻的两个位置球不能相同，问方案数量。这是一个经典容斥题，我们考虑假设第 $i$ 种球出现了 $j$ 组相邻，那么就把这些球缩在一起。现在就变成了有 $i-j$ 个球进行排列，乘上容斥系数 $(-1)^{j}{i-1 \choose j}$ 。 回到这个题，我们现在希望确定的是每种颜色的球的分段情况。一旦我们确定了分段情况，就变成了上面那个问题。 我们先不扩 ...

我们考虑当 $a_ia_j,a_ja_k$ 均为完全平方数的时候，$a_ia_ka_j^2$ 也一定是一个完全平方数，于是 $a_ia_k$ 也是完全平方数了。也就是说我们可以把所有数划分成很多类，每一类里面任意两个数乘起来都是完全平方，并且不同类的数乘起来一定不是完全平方。 如果把 “同一类” 这个问题看成 “同一种颜色”，现在问题就在于给定很多个数，每个数有自己的颜色，求排列数量满足不存在相邻的相同颜色的数。 这是个经典的容斥问题，可以考虑枚举不满足这个条件的相邻的数的数量。具体来说，我们分 ...

A 没啥意思 B 不会 nim 积 就不写题解了。 我们考虑什么时候先手必赢。我们分直径的奇偶来讨论。 如果直径长度是奇，那么一定存在一个直径中点。假设开始的时候棋子在直径中点，那么先手不管怎么跳，后手都可以跳到直径上与终点对称的那个方向，于是先手就 GG 了。否则，假设开始不再直径中点，先手显然可以一次让棋子到直径中点，后手就 GG 了。 如果直径长度是偶，那么这个时候相当于有两个终点。先手可以跳到离根较远的那个中点上，于是后手必然不能通过模仿棋走到另一个中点，这个时候先手又可以和后手下模仿棋 ...

长链剖分是一种比较冷门的科技。算法本身很简单，就是把重链剖分中的权值（子树大小）变成子树内的最大深度。显然，长链剖分复杂度是 $O(n)$ 的，它和任何剖分一样，会把树剖分成 $O(n)$ 条链，并满足链长和 $O(n)$。 一般用来做下面两件事情： 树上 k 级祖先以前写过，后来咕咕咕了的东西。 显然，我会倍增。复杂度 $O(n\log n + Q\log n)$ 。 但是长链剖分可以做到线性回答询问，复杂度可以是 $O(n\log n + Q)$ 。当然通过某些神仙科技（四毛子算法）可以做大 ...

胎教级入门篇 还是没有详细的证明。。 Burnside 定理（烧边定理（？大雾）） 对于一个置换 $f$，我们定义 $C(f)$ 为 在合成 $f$ 后保持相对于原来不变的方案数量，这里称作 不动点。不动点并不是一个点，而是一个方案！ 以染色为例，“不动点”即指染色方案，满足合成 $f$ 后染色不变。 那么本质不同的方案数量就是对于左右可用置换不动点个数平均值，形式化地写： ans = \frac 1 {|G|} \sum_{f \in G} C(f)其中 $G$ 是一个置换群。 Polya ...

改不动 BC 了 /kel 4.4 模拟赛 A签到失败。 题目链接 显然只需要考虑第一个点为 $1$ 的情况，其他情况的方案数量是一样的。 一个合法的排列等价于在树上走，走到一个点时可以标记它，除了 $1$ 每个点只被标记一次，从 $1$ 开始在 $1$ 结束， $1$ 在开始和结束时各被标记一次，且两次标记间的路径是简单路径。 我们考虑题目给的删完所有边权的条件，就是每个点被经过 $\frac{\sum_v w(u,v)}{2}$ 次。 对于每个点 $u$ 我们考虑这样构造一个序列 $S_u$ ...

更新了两道例题辣 多项式板子见另一篇博文。 Orzlsj 定义 普通生成函数 OGF 对于数列 $\{a_i\}$ ，OGF 是： A(x) = \sum_{i\ge 0} a_ix^i 指数生成函数 EGF EGF 是： A(x) = \sum_{i\ge 0} a_i\frac{x^i}{i!} 这两个有什么用？ OGF 一般解决无标号有序的问题，EGF 一般解决有标号有序的问题。 OGF两个 OGF 的乘积 $A(x)\times B(x)$ 可以理解为 从 $A$ 中选择一 ...

P2093 [国家集训队]JZPFAR我们考虑建立 KDT 。我们可以维护一个 堆 表示前 $k$ 远的点组成的小根堆。 然后到达每个点看看是否能够加入堆就好了。 进入子树的时候也得先进距离大的，如果到矩形最大距离都不如当前最小的就 skip 就好了。不加这两个剪枝稳被卡。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606 ...

暂时只更了 多项式求逆 ，多项式 Ln ，多项式 exp。。 多项式求逆众所周知，一个多项式求逆后是一个无穷次项的玩意。但是我们一般只需要它的前 $n$ 项。 我们需要算出： A\times B \equiv 1 \pmod {x^n}这东西怎么做？背板 我们可以考虑倍增来求解。 首先如果 $A$ 仅有一项，那么 $B[0]$ 就是 $A[0]$ 的逆元。 否则，假设我们已经有了 A\times B' \equiv 1\pmod {x^{\lceil\frac n 2\rceil}}\\同时 ...

CF1120D Power Tree首先这题有个非常显然的做法。考虑自深向浅放点，那么当决定在 $u$ 是否放点的时候子树内的叶子都被正好一个观察点覆盖或者只有一个没有被覆盖。否则是无法完成题目的条件的。所以我们可以 $dp[u][0/1]$ 表示 $u$ 子树内有 $0/1$ 个剩下的点做一次树形 dp。 可是还有一个更加优秀的做法。 我们考虑这个操作的本意其实是区间进行 + / - 。根据 NOIP 2018 的经验我们知道这个东西很多时候会转化成差分的 + 或者 - 。于是我们考虑把叶子提 ...

CF1000F One Occurrence我们考虑离线询问，然后按照右端点排序来处理。对于当前的右端点，我们对每个值维护当询问左端点 $L$ 在一个区间（这个值最后一次出现到倒数第二次出现的位置之间），这个值就不是出现一次的。所以我们考虑的就是当前左端点是否被至少一个这种值覆盖。于是有了个显然的 2log 做法，每个点维护一个 set。。然后就 get 了一个 TLE。 于是考虑我们可以建立线段树表示当某个原数组位置的值想要作为右端点左端点得是多少。于是就变成了一个区间取最小值的问题。 123 ...

Orzwkr P4220 [WC2018]通道一眼看上去和 暴力写挂 类似，可是从两棵树变成了三棵树了。 看起来，暴力写挂好像两棵树是极限了，但是这题它满足 $w$ 非负，所以直径是可以合并的。 还是考虑第一棵树上边分，化下式子成为 di s(rt,u) + dis(rt,v) + dep_2[u]+dep_2[v]-2dep_2[lca_2(u,v)]+dis_2(a,b)于是还是考虑根据边分把两边分成两种颜色，然后在第二棵树上建立虚树来 $dp$ 。然后考虑怎么维护当前子树内不同颜色的点在 ...

真 · 边分治从入门到入土。。 P4565 [CTSC2018]暴力写挂神仙题。。 我们考虑化一下式子，同时设 $dep[x]$ 为第一棵树的深度，$dep_2[x]$ 为第二棵树的深度，$dis(x,y)$ 为两个点在第一棵树的距离，于是去掉第一棵树上的 LCA : f(x,y) = \frac 1 2 (dep[x] + dep[y] + dis(x,y)+dep_2[LCA_2(x,y)])由于深度这个东西显然可以三度化来做的，考虑在第一棵树上边分治，对每个点维护 $dep[x] + d ...

边分治边分治是类似点分治的一种树分治方法。顾名思义，边分治就是用边来分治。我们每次找的边也就是两边 size 最大值尽量小的边。同样的，边分治的过程也是把树分成了很多联通块，只是对边打标记罢了。 但是，直接边分复杂度是假的，可以参考菊花图直接卡成 $O(n^2)$ 。我们可以对所有儿子分别建立一个虚点，从上一个儿子的虚点向下一个儿子的虚点连 $0$ 边。这样做后会发现所有点的度数都变成了 $3$ ，所以称之为三度化。 三度化后边分治的过程中的时间复杂度分析大概是 $T(n) = O(n) + T ...