nfls 近期题目总结

· · 个人记录

2023/11/16

C.动物园的尺子

题面：不重要。

Trick：用 [0,n-1] 构建长度为 n 的格雷码

格雷码：相邻两位的格雷码二进制表示下只有 1 个不同的位置。

先考虑构造长度为 2^n 的格雷码，考虑倍增构造，假设已经构造出了长度为 2^{n-1} 的格雷码，考虑将两个长度为 2^{n-1} 的格雷码拼在一起。

先把后面整体加上 2^{n-1}（相当于最高位变成了 1），然后再整体翻转过来拼到前面那段上。

考虑到拼接处只有第 n-1 位不相同，于是构造好了。

再考虑长度部位 2^n 的格雷码，先把 n 二进制分解，然后由大的二进制位一直拼到小的二进制位，考虑两段拼接：

后面那段是长度为 2^{k}，前面那段是若干个 >k 的 2^x 拼在一起，分别设为 n,m。

然后我们可以先将后面那段整体加上 m，满足互不相同，考虑拼接处，由于前面最后一个数满足前面那些较高的位除了 lowbit(m) 都为 1，然后可以将前面那段整体异或上一个数，使得拼接处不同的位恰好为 lowbit(m)，最后拼起来即可，由于异或的数不会超过 lowbit(m)，所以前面那段的值域不会发生变化。

2023/11/14

D.重逢

简要题意：

有 n 种石子，第 i 种石子有 a_i 颗，保证石子总个数为偶数。

现在 Alice 要将石子分为个数相等的两堆，然后和 Bob 在分出来的两堆分别进行游戏，其中第一堆 Alice 先手，第二堆 Bob 先手，最终 Alice 的得分为两个游戏得分相加。

游戏如下：两个人依次取石子，设 Alice 最终取了 b_i 个第 i 种石子，则 Alice 得分会加上 \lfloor \dfrac{b_i}{p_i}\rfloor\times val_i。

Alice 想让自己得分最大，Bob 想让 Alice 总得分最小，问最后的得分。

\sum a_i\le2\times10^6,n\le2000,\sum p_i\le2000

首先考虑一堆固定的石子如何计算最后的得分，考虑当前操作的人的策略。

按目前剩下的石子个数分类：

按照这个思路，我们可以写出一个简单的背包形式，记下第一堆分了多少个石子，目前两堆谁是先手的最大答案。

复杂度 O((\sum a_i)^2)

考虑优化，容易发现对于一堆整的 2p_i，分到左边和右边对答案的贡献是一样的，那么我们考虑先分配余数，这样背包是 O((\sum p_i)^2) 的。

然后考虑剩下整的部分背包，由于 \sum p_i 有限制，那么本质不同的 p_i 最多只有 O(\sqrt{\sum p_i}) 种，然后跑背包的复杂度就是 O(\sqrt{\sum p_i}\times\sum{a_i}) 了（由于只用记录可行性，可以对于每个 i 记下要达到 i 至少要多少个当前的数）。

或者也可以用二进制分组 + bitset 优化做到 O(\dfrac{\sqrt{\sum p_i}\times\sum{a_i}\times \log{\sum{\dfrac{a_i}{p_i}}}}{w})。

2023/11/13

D.人赢

简要题意：有 n 个点，点有点权，定义边权为两个点的异或值，问把原图连成若干个环（即每个点度数为 2）,使得边权的最小值最大，问这个最大的最小值。

### Trick1：拆点变为二分图匹配 考虑把环上的边定向，现在变成了每个点出度和入度都为 $1$。 那么把点拆成入点和出点，每条边相当于入点匹配出点，然后题目要求即变成新图的完美匹配。 考虑二分答案，现在就是要快速判断图有没有完美匹配。 考虑 Hall 定理，图存在完美匹配当且仅当 $min(|f(S)|-|S|)>=0

考虑 Trie 上 dp 贪心，设 f(x,y) 表示 x 子树内选个点集 S，S 和 S 在 y 子树内的邻域 f(S) 的 |f(S)|-|S| 的最小值。

若 mid 当前位为 1，那么 f(x,y)=f(son_{x,0},son{y,1})+f(son_{x,1},son{y,0})。

若 mid 当前位为 0，那么分讨一下可得：

x$ 左右儿子都不选：$0 $x$ 只选左/右儿子：那么 $y$ 的右/左儿子一定会成为邻域，剩下的部分可以递归，即 $siz_{son_{y,1}}+f(son_{x,0},son{y,0}))$ 或者 $siz_{son_{y,0}}+f(son_{x,1},son{y,1}))$。 总复杂度 $O(nlog^2n)

2023/11/11(SNOI2020)

P6790 [SNOI2020] 生成树

简要题意：给定一个多一条边的仙人掌，问这个图生成树个数，n,m\le5\times 10^5。

Trick：广义串并联图

定义：缩边后不存在 4 个点的完全图的图。

性质：可以通过删一度点，缩二度点和删重边使图变成单点。

做法：考虑按上面的操作把原图变成单点，记 f_i 表示某条边保留的方案数，g_i 表示某条边不保留的方案数。

删一度点：此时这条边必须保留，答案乘上 f_i。

缩二度点：此时保留这条新边就必须两条都保留，f_{i'}=f_i\times f_j，不保留新边要恰好保留一条（否则不连通），g_{i'}=f_i\times g_j+g_i\times f_j。

删除重边：此时保留这条新边就必须恰好保留一条，f_{i'}=f_i\times g_j+g_i\times f_j，不保留新边要两条都不保留，g_{i'}=g_i\times g_j。

按照度数进行操作即可，复杂度可以做到线性。

P6791 [SNOI2020] 取石子

简要题意：Fibonacci Nim 的基本条件下，限制先手第一次取的个数，问 1-n 有多少个状态先手必胜。

Trick：Fibonacci Nim

简要规则：先手第一次可以取 [1,n-1] 个石子，然后若上一个人取了 i 个石子，则下一个人只能取 [1,2i] 个石子，不能取的人输。

结论：当 n 为斐波那契数时，先手必输，否则先手必胜。

先考虑证明 n 为斐波那契数时，先手必输。

考虑归纳法：

首先，显然 n=1,2,3 时先手必输。

考虑 n>3 的情况：

已知 F_1,F_2,\cdots,F_n，设 n=F_{i+1}，考虑先手第一次取 x 个石子。

首先 x\lt F_{i-1}，因为 2x\ge 2F_{i-1}\gt F_i = F_{i+1}-F_{i-1}\ge n-x，否则后手可以一次取完。

考虑后手策略，后手可以恰好取完 F_{i-1}，并使先手不能取完 F_{i}，然后进入下一个必败态。

那若 x\ge\dfrac{F_{i-1}}{3}，则后手可以取 F_{i-1}-x，此时 2(F_{i-1}-x)\le\dfrac{4F_{i-1}}{3}=F_{i-1}+\dfrac{1}{3}(F_{i-2}+F_{i-3})=F_i-\dfrac{2}{3}F_{i-2}+\dfrac{1}{3}F_{i-3}，这玩意显然小于 F_i。

因此此时进入了上面后手想要的必败态。

否则又可以将 F_{i-1} 分为 F_{i-2} 和 F_{i-3}，因为 F_{i-3}\ge\dfrac{1}{2}F_{i-2}\ge \dfrac{F_{i-1}}{3}\gt x，所以先手无法一次取完 F_{i-3}，所以现在游戏又变成了后手要恰好取完 F_{i-3} 且不让先手一次能取完 F_{i-2}。

然后又可以一直分下去直至 corner case，然后最后先手无法不取，最后再往前推直至 F_{i+1} 先手必败。

考虑证明 n 不为斐波那契数时，先手必胜。

定理：任意一个数可以分为若干个不相邻的斐波那契数之和。

证明：考虑归纳法：

首先 n 为斐波那契数时，成立。

否则，设 F_i 为最大的小于等于 n 的斐波那契数，因为 n\lt F_{i+1}，所以 n-F_i \gt F_{i-1}，又因为 n-F_i 能表示成若干个不相邻的小于 F_{i-1} 的斐波那契数的和，而且这些数不可能和 F_i 相邻，最后得证。

推论：容易发现这样的方案是唯一的。

设 n=\sum_{i=1}^{k}F_{c_i}(k\ge2)，则先手先取 F_{c_1}。

因为 F_{c_2}\ge F_{c_1+2}=F_{c_1}+F_{c_1+1}\gt2F_{c_1}，因此后手不可能取完 F_{c_2}，则考虑把 F_{c_2} 变成个单独的 Ficbonacci Nim，由结论得此时最后一个石子会被先手取走，然后此时后手无法取完 F_{c_3}，依次类推，每个 F_{c_i} 都会被先手取走，则最后一个石子也会被先手取走。

证毕。

推论：由证明过程可知先手能获胜当且仅当 k\ge F_{c_1}。

计数是简单的，此处不展开讨论。

2023/11/10

D.摩拉克斯

题意：给定一棵树，边有边权，点有点权，在树上找两个点 A,B，使得树上所有点到 A,B 的较短的那个距离乘上点权之和最小。n\le10^5，\sum n\le5\times10^5

首先考虑贡献如何计算，首先一定 A 到 B 的路径上一定存在一条分界边，满足这条边一侧的节点距离 A 更近，另一侧距离 B 更近。

于是我们枚举分界边，相当于某个点子树内选一个带权重心，子树外选一个带权重心。

Trick：一个点的带权重心必然在根的重链上，且为重链上第一个子树大小 \ge n/2 的点。

证明显然。

那么子树内的重心可以通过 dp 求出，可以从重儿子转移过来，然后暴力向上跳，可以证明这样做均摊是 O(n) 的。

但是求子树外的重心时，由于删掉了某棵子树，可能导致根所在重链发生变化。

考虑钦定原树重心为根，此时，若这个子树在根的轻子树内，那重心在原来的重链上，否则在原来的根的次重链上。

考虑证明，前者显然，因为重链不发生变化，后者因为你删掉了原来重子树内的点，那么原树的重心肯定往远离这个子树的方向偏离，那此时重链就会发生切换变为原来的次重链。

在对应的链上二分即可，复杂度 O(nlogn)。

2023/11/9

C.最短路

简要题意：给定一个 n 个点 m 条边的有向图，定义路径权值为路径上所有相邻边 x,y 的 cost(w_x,w_y) 之和，其中 cost(x,y)=\sum_{i=1}^{k}c_ix^{a_i}y_{b_i}，其中 a_i,b_i,c_i,k 为常数，求单源最短路。 n,m\le2\times 10^5,k\le5,a_i,b_i,c_i \texttt{是正整数}

Trick： dijkstra 点转边

考虑 dijkstra 的过程中，每个点会松弛若干个点，然后将这些点加入队列。

但现在路径权值还要记上上一条边的权值是什么，不妨把边看作状态记 f_i 表示最后走的边是 i 的最短路。

按照 dijkstra 的思想，每次选出最短路最小的状态进行松弛，但一次松弛要松弛那条边的端点的所有出边，这样做复杂度会退化到 O(d^2)，其中 d 表示度数。

考虑到每个点的出边肯定是按 w_i 从小到大依次松弛，这很好理解，因为在入端点相同时，w_i 越小，f_i 必然越小。

那我们考虑只维护每个点目前未被处理的 w_i 最小的出边，对边进行松弛时，由于 cost(x,y) 具有和一次函数类似的单调性，可以用李超树维护做到 O(kmlogm)。

挂分提醒：由于本题值域只保证 cost(max_W,max_W)\le10^{18}，所以李超树值域写 10^6 可能会爆 long long，因此值域应为 \le max_W，或离散值域。

2023/11/7

D.LCM序列（数独立集权值和）

前面地转化很显然，问题变成了数独立集的权值和，复杂度要求做到 O(2^{n/2})

做法：Meet in Middle

考虑把点集分为两半，计算出两个部分内部的连边和外部的连边。

不妨设最后的独立集 S=A \cup B，考虑对于每一个确定的 A 考虑其所对应的 B 的权值和。

对于一个确定的 A 来说，其对于 B 的限制是某些点不能选，即只能在某个确定的点集 B 里选出一个子独立集 B'。

考虑计 f_B 表示点集为 B 时，其所有的子独立集 B' 的权值和，转移可以通过枚举 lowbit 是否被选做到 O(1)。

具体如下：

f_B=f_{B-lowbit}+a[lowbit]\times f_{B'}(B'\in B,B'\text{与lowbit无直接连边})

剩下的容易直接计算，最后复杂度 O(2^{n/2})。

Bonus: 图的团计数，n,m\le1000

容易发现 \text{图的团的个数}=\text{补图独立集个数}

考虑钦定每个团只会在团内编号最小的点被计算。

对每个点按度数从小到大重标号，把每条边定向为编号小的连向编号大的，把无向边变成有向边。此时每个点出度不超过 \sqrt{m}。（证明类似于三元环计数）

然后枚举每个点，把连出去的点扔进去跑补图独立集计数，每次跑独立集计数是 2^{n/2}，加起来最劣复杂度为 O(\sqrt{m}\times2^{\sqrt{m}/2})，且远远跑不满。

2023/11/1（构造题专场）

A.人生的经验

简要题意：给定一个字符集 C 和长度 l，要求构造一个长度最短的字符串 S 包含所有 |C|^l 种长度为 l 的字符串。（|C|^l\le10^7）

Trick：哈密顿路径转欧拉路径

考虑把每种字符串看作一个点，向后加一个字符相当于可以走一条边走到另一个状态，现在问题就变成了求一条最短的哈密顿路。

但是哈密顿路显然是 NPC 的问题，考虑改成记长度为 l-1 的字符串前缀，每走一条边相当于出现了一个长度为 l 的字符串，现在问题就变成了每条边都经过至少一次。

容易发现这个图是欧拉图，入度和出度都是 |C|，直接跑欧拉回路即可。

D.Hby的旅游之都

简要题意：给定一个 DAG，要求你给图上的边染 RGB 三种颜色之一，使得图上不存在连续经过 42 次同一种颜色的路径。n\le5\times 10^4

确定性构造

考虑对于 DAG 的拓扑序进行处理，可以发现只会从拓扑序小的点向拓扑序大的点连边。

考虑每 42 个点分一个小组，每 42 个小组分一个大组，小组内连边 R，大组内连边 G，大组间连边 B。

考虑到走 42 条边一定会走出小组，所以不存在连续相同的 R，同理不存在连续的 B 和 G。

E.单调上升序列 && F.皇后平板

简要题意：给定一个 n 个点的完全图，要求给图上的边赋值一个 [1,\dfrac{n\times(n-1)}{2}] 的边权，使得图中连续单调上升路径最短。

分析：答案下界显然是 n-1，因为考虑到 n 个点的完全图有 \dfrac{n\times(n-1)}{2} 条边。

假设每个点上都有一个旅行者，考虑从小到大考虑每条边，考虑到某条边时把那条边的两个旅行者交换位置，最后 n 个旅行者一共走了 n\times(n-1) 步，根据鸽巢原理，每个旅行者最少走了 n-1 步。

Trick：n 个点拆出 n-1 组完美匹配（n 为偶数）

即可以把一个完全图分成 n-1 组完美匹配，满足每条边恰好出现在一组完美匹配中，且完美匹配不交。

一种构造方式如下，考虑枚举每组完美匹配与 n 连边的点 u，在这组中 u-i 会与 u+i 连边，可以证明两个点只会在它们的对称中心被连恰好一次边。

回到正题，我们可以把边权也分成 n-1 组，每组 \dfrac{n}{2} 种边权，其中第 i 组边权为 [\dfrac{n}{2}(i-1)+1,\dfrac{n}{2}i]。

然后我们将每一组边权填入一组完美匹配，因为完美匹配中的边两两不相邻，所以不存在一条单调上升路径同时走同一组完美匹配中的边，又因为完美匹配的组数为 n-1，所以最长单调上升路径的长度不超过 n-1，达到下界。

Extra：F. 皇后平板

简要题意：要你构造一个 n\times n 的矩阵，满足第 i 行和第 i 列数的并为 [1,2n-1]。

容易发现奇数时无解，考虑偶数的情况。

考虑对角线都填上 1，此时剩下的格子要填入 [2,2n-1] 这 2n-2 个数。

考虑把这些数分成 n-1 组，每组两个数，然后又因为 n 是偶数，恰好有 n-1 组完美匹配。

考虑第 i 组完美匹配的边 (i,j)，在 (i,j) 处填入 2i，在 (j,i) 处填入 2i+1，不难证明这样构造是合法的。

2023/10/31

B.小 G 的布料

给定一个 01 矩阵，求面积 \ge K 的全 0 矩阵个数。

Trick\;1：子矩形唯一确定法

这类对子矩形计数问题，首先要确定用什么确定一个子矩形。

常规的题目大多都是枚举右下角然后确定矩形。

我赛时突发奇想，对于这种全 0 矩阵，假如确定了最下面一行，那一定会有某一列会“卡”住这个矩形的高度，不妨称之为“瓶颈列”。

考虑记 f_i 表示第 i 列往上连续的 1 的长度，则“瓶颈列”就是在子矩形中 f_i 最小的那一列（如有相同则选靠左的）。

则考虑枚举最下一行和瓶颈列，则每个瓶颈列可以向左和向右延申一段距离，可以用单调栈或笛卡尔树求出。

然后现在问题相当于左端点可以在 [L_i,i]，右端点可以在 [i,R_i]，然后高度为 [1,j] 中有多少个子矩形大于 K，左右端点限制很麻烦，考虑容斥，用全部的减去只在左边或只在右边的答案。

然后剩下的计算可以预处理，不多赘述。

D. LCM Game

对于 n^k 种长度为 k，值域在 [1,n] 的序列里，求出每个序列的 LCM 之和。（求积是萌萌题）

--- ### $Trick\;1$：$LCM$ 变 $max$ 卷积 + FWT $LCM$ 本质上就是对每个质数的幂次求 $max$，于是状态可以由记 $LCM$ 变成记每个质数取的最高次数，可以变成一个集合幂级数的形式。 在 $n\le 60$ 时，本质不同的状态只有约 $2\times 10^6$ 种。 然后考虑对其进行 $FWT$，然后可以求出 $LCM$ 为 $x$ 的因数方案数（本质上是 $max$ 卷积），最后再 $IFWT$ 回去。 ### $Trick\;2$：大小质数分治（[P2150 [NOI2015] 寿司晚宴](https://www.luogu.com.cn/problem/P2150) 和 [P8292 [省选联考 2022] 卡牌](https://www.luogu.com.cn/problem/P8292)） 考虑到对于大于 $\sqrt{n}$ 的质数的最高幂次只有 $1$，且不可能一个位置同时存在两个大于 $\sqrt{n}$ 的质因数。 于是可以对于大于 $\sqrt{n}$ 的质数进行 $dp$，设 $f_{S,i}$ 表示小质数的状态为 $S$，且目前可以选的数由 $i$ 个的大质数乘积之和。（$f$ 数组是进行过 $FWT$ 后的形式） 考虑到确定某个大质数一定被选很难，考虑容斥，选的贡献为 $p$，不选的贡献为 $1-p$。 最后和只选小质数的合并起来即可。 为了优化状态，可以发现在选了大于 $\sqrt{n}$ 的质数时，剩下的小质数的幂次会略小一点，可以进行剪枝。 复杂度 $O(960n^2+69984n)$。 ## 2023/10/29 ### [P6009 [USACO20JAN] Non-Decreasing Subsequences P](https://www.luogu.com.cn/problem/P6009) 简要题意：多次询问区间不下降子序列个数。（$n\le 5\times 10^4,q\le10^5,k\le20$，$k$ 为值域）。 ### $Trick\;1$：矩阵转移 设 $f_{i,j}$ 表示当前考虑完前 $i$ 个位置，最后结尾为 $j$ 的方案数，容易写出转移矩阵，且用线段树优化可以做到 $O(nlognk^3)$。 对于不带修，可以猫树分治做到同样的复杂度，同时发现转移矩阵只有 $O(k)$ 个位置有值，所以可以做到 $O(nlognk^2+qk)$。 ### $Trick\;2$：前后缀矩阵求逆以及转置 设 $P_i$ 表示 $i$ 位置的矩阵，则答案可以表示为 $(\prod_{i=l-1}^{i\ge1} P'_i)\;·\;(\prod_{i=1}^{r}P_i)$，后面的可以直接预处理。（$P'$ 表示 $P$ 的逆矩阵） 首先我们要知道 $P'_i$ 是什么，$P_i$ 相当于在单位矩阵的基础上，在第 $a_i$ 列的 $[1,i]$ 行加上了 $1$，则 $P'_i$ 则是在单位矩阵的基础上在这些位置加上了 $-\dfrac{1}{2}$。 但是我们发现乘起来是逆序乘起来，而矩阵乘法没有交换律，这样也很简单，可以先把要求的东西转置一下，则转置完后乘法顺序倒了过来，最后再转置回去即可。 预处理可以做到 $O(nk^2)$，询问由于要先乘一个向量，所以说询问可以做到 $O(qk^2)$，加上前缀和优化可以做到 $O(qk)$。 ## 2023/10/27 ### D.灵活性（[P5642 人造情感（emotion）](https://www.luogu.com.cn/problem/P5642)） 简要题意：给定一棵树和若干条带权路径，多次询问在某个虚树连通块不选的情况下能选出的路径两两不交的路径集合的最大权值。 --- ### $Trick\;1$：全局最大值 考虑维护 $f_u$ 表示 $u$ 子树内路径集合的最大权值，记 $s_u=\sum_{v\in son_u}f_v$。 考虑把每条路径放在 $LCA$ 考虑。 若 $u$ 不作为 $LCA$ 被覆盖，则 $f_u=s_u$。 若 $u$ 作为 $LCA$ 被覆盖，设路径为 $(x,y)$，则 $f_u=s_u+\sum_{v\in(x,y),v\neq u}(s_v-f_u)+w(x,y)$。 即钦定 $(x,y)$ 路径上的点都不能选，然后求最大值。 可以用线段树或者树剖维护。 --- ### $Trick\;2$：部分不选最大值 和上面类似，但是要考虑上虚树的根的子树外的贡献。 设 $g_u$ 表示 $(u,fa_u)$ 这条边没被覆盖的最大集合权值。 考虑转移，要么 $fa_u$ 没被选，则 $g_{u}=g_{fa_u}+s_{fa_u}-f_{fa_u}

否则，考虑 fa_u 是被哪条路径覆盖的，考虑在路径的 LCA 处计算。

假设在 u 处选了 (x,y) 这条路径，则可以贡献到的点 v 满足 fa_v\in(x,y),v\notin (x,y)，贡献的值为 \sum_{v\in(x,y)}(s_u-f_u)+w(x,y)+g_u。

可以用树链剖分打标记维护，考虑在父亲处记下儿子的标记，考虑记 (w,u,v) 表示这次打的标记的权值是 w，且不能传给 u 和 v 两个儿子。

计算时将父亲的标记排序，然后暴力扫一遍选最大的，找到直接退出，可以发现这样每个标记只会被扫到 O(1) 次。

考虑到对于那些父亲在同一条重链上的点，标记都是 (w,bson_u,0) 的形式，可以用线段树维护，则这样只有切换轻重链才要暴力打标记，一共只会暴力打 O(logn) 个标记。

总复杂度 O(nlog^2n)，查询可以做到单次 O(logn)（虚树）。

2023/10/24

D.净土裁断（出题人玩原神，但不多）

简要题意：树上随机游走，求每个点走到根的距离的 k 次方的期望。

Trick\;1：树上随机游走

常用做法：树上高消

设 f_u 为树上随机走到根的期望步数，可得方程：

f_u=1+p_uf_u+\dfrac{1-p_u}{d_i}\sum_{(u,v)\in E} f_v

考虑把 f_u 表示成 A_uf_{fa}+C_u 的形式。

把儿子和父亲分开考虑，

f_u=1+p_uf_u+\dfrac{1-p_u}{d_i}(f_{fa}+\sum_{v\in son_u}A_vf_u+C_v)

把常数整理即可得到 f_u=A_uf_{fa}+B_uf_u+C_u 的式子，然后把 B_uf_u 移项然后得到 f_u=\dfrac{A_uf_fa+C_u}{1-B_u} 作为新的 A_u 和 C_u。

最后由于 f_{root}=0 可以 dfs 一次求出答案。

Trick\;2：期望 k 次方公式

有两种拆法：

  1. 用二项式定理：
E((a+b)^k)=E(\sum_{i=0}^{k}\binom{k}{i}a^ib^{k-i})

变成 EGF 后是卷积的形式。

  1. 用斯特林数拆幂：
E(x^k)=E(\sum_{i=0}^{k}\binom{x}{i} S(k,i) i!)

证明：

考虑枚举最后染色出的颜色的集合大小 $i$，可以在 $x$ 种颜色选 $i$ 种，方案为 $\binom{x}{i}$，再把 $k$ 个球划分到 $i$ 个集合里，方案为 $S(k,i)$，由于集合是无序的，所以要乘上 $i!$。 这样子拆的好处是我们只要求出 $E(\binom{x}{i})$ 的期望就行了。 而这个东西的期望满足 $\binom{x+1}{i}=\binom{x}{i}+\binom{x}{i-1}$，即可以 $O(1)$ 加上 $1$。 ### 最终解法 观察到 $f_{u,i}=E(\binom{x}{i})$ 是分层的，即 $f_{u,i}$ 只和 $f_{u.i-1}$ 有关，可以 $i$ 从小到大依次求，这样计算 $f_{u,i}$ 时 $f_{u,i-1}$ 可以看作常数，用树上随机游走式子即可，复杂度为 $O(nk+k^2)$，用多项式预处理斯特林数可以做到 $O(nk+klogk)$。 ### 补充: - $(\sum{x_i})^k

这个东西的组合意义是 k 个人里每个人可以选择一个物品（可重复选择），物品有权值，一个方案的权值为所有人的物品的乘积，问所有方案的权值之和。

形式化地讲：

(\sum{x_i})^k=\sum [\sum t_i=k]\binom{k}{t_1,t_2,\cdots,t_n} \prod x_i^{t_i}

其实就是把 e^{x_i} 的 EGF 卷起来，然后求 [x^k]F(x)。

例题：P7483 50 年后的我们

2023/10/23

D.乘积

简要题意：

设 n=\prod_{i=1}^{k} p_i ，即若干互不相同的质数的乘积。

设 f(n)=\prod_{i=1}^{m}\sigma_{x_i},\prod_{i=1}^{m}x_i=n ，其中 m_0 是常数。

设 g(n)=\prod_{i=1}^{m}Ax_i^2+Bx_i+C,\prod_{i=1}^{m}x_i=n ，其中 m_1,A,B,C 是常数。

要计算 \sum_{m|n}f(m)g(m)，其中 k\le100；m_0,m_1\le10^{18}。

Trick\;1：二次函数变积性函数。

二次函数 Ax^2+Bx+C 不是积性函数，但是二次函数的每一项 x^2,x,1 都是积性函数。

对于计算像 g(n) 这样的函数，可以从依次把每个质数填入，可以选择新开一个 x_i，也可以选择填入已经被填过的 x_i。

对于 \prod_{i=1}^{m}Ax_i^2+Bx_i+C 可以用组合意义拆开变成每个 x_i 可以选择零次项，一次项，二次项其中之一，然后问最后所有选择方案的价值之和。

钦定每个被填过的 x_i 在被填入第一个数时就确定了状态。

记 f_{i,j,k} 表示目前分别有有 i,j,k 个坑选了零次项，一次项，二次项的价值之和。

转移显然。

最终解法

考虑在计算 g(n) 的时候把 f(n) 的贡献算进去。

最终复杂度 $O(k^4)$。