记录最近乱做的一些 CF 题目.
1361B Johnny and Grandmaster
给定 $n,p$ ,以及 $n$ 个数,第 $i$ 个数是 $p^{k_i}$ ,你需要将它们划分入两个集合,使得两个集合内的数总和之差最小.
$1\le n,p\le 10^6, 0\le k_i\le 10^6$ ,答案对 $10^9+7$ 取模.
可以看成是对每个数确定贡献是 $p^{k_i}$ 还是 $-p^{k_i}$ ,最小化总贡献的绝对值.
将所有数按照 $k_i$ 从大到小排序,依次考虑,维护一个当前贡献 $s$ ,若 $s>0$ ,则减掉当前数,否则加上当前数.
简单的想法是用 $p$ 进制高精度去模拟这个过程,但 $n,k$ 都很大,这样实现会超时.
注意到当 $v=\frac{s}{p^{k_i}}>n$ 时,后面考虑的数一定都是被减掉的,于是只用维护这个 $v$ 的值即可.
需要特判 $p=1$ 的情况.
时间复杂度 $O(n\log n+n\log k)$ .
code
1361C Johnny and Megan’s Necklace
有 $2n$ 个点,其中 $2i-1$ 与 $2i$ 已经有边,你需要再连出一些边让这个图成为一个环.
每个点有权值 $a_i$ ,连接 $i$ 与 $j$ 的收益是 $\log_2({\rm lowbit}(a_i\operatorname {xor} a_j))$ ,特别地,若 $a_i=a_j$ ,则收益为 $20$ .
一个方案的总收益是所有你连接的边中收益的最小值.需要求出最大的总收益,并给出一个合法的连边方案.
$1\le n\le 5\times 10^5,0\le a_i<2^{20}$ .
首先可以二分答案 $k$ ,那么就只有后 $k$ 位相同的点之间可以连边,要连出一个大环.
将原有的每条边,以及 $2^k$ 种权值看作新的点,原有的每个点看作新的边,连接它后 $k$ 位的权值以及原来与它相邻的边.
于是在转化后的图上找出一条欧拉回路,就等价于在原图中连出了一个大环.
时间复杂度 $O(\log \log a\cdot n+a)$ .
code
508D Tanya and Password
一个长度为 $n+2$ 的字符串有 $n$ 个长度为 $3$ 的子串,现在给你 $n$ 个长度为 $3$ 的串,问能否还原出一个合法原串.
若能还原出原串,还需要输出任意一个合法的方案. $1\le n\le 2\times 10^5$ .
若两个节点满足 “某个结构相同” 时有边,要找哈密尔顿路径,通常可以将节点当做连接结构之间的边,找欧拉路径.
其实和上面那道题很像.若一个串的前两位和另个串的后两位相同,则可以接在它的后面.
将每种长度为 $2$ 的串当作点,每个给出的串从它前两位的点向后两位的点连边,求此有向图的欧拉路径即可.
时间复杂度 $O(n)$ .
342E Xenia and Tree
给定一棵 $n$ 个点的树,每个点是红色或者蓝色,初始时只有 $1$ 为红色.有 $m$ 次操作,可能是修改或询问.
修改:将蓝点 $x$ 变成红点.询问:询问 $x$ 到所有红点中最小的距离.
$n,m\le 10^5$ .
显然直接写个动态点分治上去就完了,不过这题只有加点操作,而没有删点操作,所以还可以定期重构来做.
对于每 $\sqrt m$ 个操作一起处理,先 bfs 预处理出每个点的答案,加入红点时将它记录下来,询问时考虑记录的红点贡献.
预处理 ST 表实现 $O(1)$ 查询 LCA ,时间复杂度 $O(n\log n+(n+m)\sqrt m)$ .
code
512D Fox And Travelling
给定一个 $n$ 个点, $m$ 条边的无重边自环的无向图,每次可以删掉一个度数 $\le 1$ 的点以及它连出的所有边.
对于每个 $k\in [0,n]$ ,需要求出有序地删掉 $k$ 个点的方案数.
$n\le 100$ ,答案对 $10^9+9$ 取模.
首先可以剥叶子预处理出哪些点可能被删掉,哪些点不可能被删掉.
若仅保留可能被删掉的点,则图变成了一个森林,对于每棵树考虑其方案数,最后卷在一起得到答案.
对于一棵树,若某个点与不可能被删掉的点有边,则它在这棵树中一定是最后被删掉的,以它为根做一个树形 dp.
设 $dp(i,j)$ 表示在子树 $i$ 中有序删掉 $j$ 个点的方案数,转移时就是将两个子树的 dp 值卷起来.
若一棵树中不存在这样的点,就以每个点为根做一次 dp, 此时若 $i$ 个点删了 $j$ 个点,会被算 $i-j$ 次,需要除掉.
时间复杂度 $O(n^3)$ .
code
449D Jzzhu and Numbers
给出一个大小为 $n$ 的可重集合,需要从中选出一个非空子集,使得子集中的数按位与的结果为 $0$ ,求方案数.
$1\le n\le 10^6$ ,元素大小 $0\le a_i\le 10^6$ ,答案对 $10^9+7$ 取模.
考虑容斥,枚举某些位,钦定这些位置按位与起来是 $1$ ,这等价于子集中每个数都是某个数 $S$ 的超集.
高维前缀和预处理有几个数是 $S$ 的超集即可,时间复杂度 $O(n+a\log a)$ .
code
55D Beautiful Numbers
给定 $l,r$ ,问区间 $[l,r]$ 内有多少个数满足它能被自己的每一个非零数位整除, $1\le l\le r\le 9\times 10^{18}$ .
考虑数位 dp, 需要记录每种数位是否出现过,若再把模每种数位的余数都记下来,状态数就太大了.
优化一下, 只需要将模 $7,8,9$ 的余数分别记录下来即可, $5$ 可以在最后一位判,其余可以用模 $8,9$ 的余数算出来.
时间复杂度大概是 $O(\log r\cdot 2^8\times 7\times 8\times 9)$ ,可以进一步优化,记录出现过的数位 LCM 即可,种类到不了 $2^8$ .
code
449C Jzzhu and Apples
给定 $n$ ,从 $1$ 到 $n$ 的整数中选出尽可能多的数对,使得每对的 $\gcd >1$ ,需要输出一种最优方案.
考虑所有满足 $p>2$ 且 $2p\le n$ 的素数 $p$ ,将它能筛到的所有数拿来匹配,若有奇数个,则将 $2p$ 留下.
最后将所有 $2$ 的幂次的数以及留下的 $2p$ 两两匹配即可,时间复杂度 $O(n\log n)$ ,魔改线性筛应该可以 $O(n)$ .
code
1368E Ski Accident
给定一张 $n$ 个点, $m$ 条边的有向图,每个点只会向编号比它大的点连边,且每个点的出度不超过 $2$ .
你需要删掉某些点以及和它们相关的所有边,使得剩下的图中不存在长度为 $2$ 的路径.
删掉的点的数目不能超过 $\frac 4 7n$ ,需要构造一个合法的方案.
按照编号顺序从小到大依次考虑每个点,若某个点此时必须被删掉,则删掉它,否则考虑下一个点.
即,对于每个点 $x$ 维护有几个点到 $x$ 距离为 $2$ ,考虑到 $x$ 时,若集合非空,则删掉 $x$ ,然后暴力更新信息.
图是一个 $3$ 层的满二叉树时显然操作次数最劣,此时 $7$ 个点中需要删掉 $4$ 个,于是删点次数不会超过 $\frac 4 7 n$ .
时间复杂度 $O(n + m)$.
code
10D LCIS
给定两个长度分别为 $n,m$ 的整数数列 $a,b$ ,求它们的最长公共上升子序列,需要输出一种合法方案, $n\le 500$ .
设 $f(i,j)$ 表示只考虑 $a$ 的前 $i$ 个数,以 $b_j$ 结尾的 LCIS 长度.
考虑转移,若 $a_i\neq b_j$ ,则只能继承 $f(i-1,j)$ 的信息.否则,转移有 $f(i,j)=\max_{1\le k<j,b_k<a_i} \lbrace f(i-1,k) +1\rbrace$ .
直接转移是 $O(n^3)$ 的.
注意到对于同个 $i$ ,随着 $j$ 增大,合法的 $k$ 形成的集合只会不断加入数,不会删除数,直接维护出最优的 $k$ 即可.
由于要输出方案,所以还需要记录一下每个状态是从哪个位置转移来的.
时间复杂度 $O(n^2)$ .
code
986C AND Graph
给定一张有 $m$ 个点的无向图和参数 $n$ ,每个点有权值 $0\le a_i<2^n$ ,两个点有边当且仅当两者权值按位与为 $0$ .
求这张图的连通块数目, $0\le n<22, 1\le m\le 2^n$ .
暴力将所有边连出来,边数是 $O(3^n)$ 的,比较爆炸,考虑优化建图.为了方便,下面直接用权值代替它的编号.
若 $x,y$ 有边,说明 $x$ 的补集应当是 $y$ 的超集,我们新建 $2^n$ 个辅助节点,记为 $0’,1’,2’\dots,(2^n-1)’$ .
那么从 $x$ 向 $x’$ 连边, $(\sim x)’$ 向 $x$ 连边,若 $a$ 是 $b$ 的超集,则 $b’$ 向 $a’$ 连边.
这样从 $x$ 出发 dfs 就能走到所有在原图中与它相连的点了.
每个 $b’$ 需要向所有超集连边,边数还是 $O(3^n)$ 的,优化一下,只向恰好比它大一个的超集连边,其他边可以传递得到.
时间复杂度 $O(n\cdot 2^n)$ ,若把边存下来,空间复杂度 $O(n\cdot 2^n)$ ,开不下,在 dfs 时直接枚举相连的点,就不用存边了.
code
1325E Ehab’s REAL Number Theory Problem
给定一个长度为 $n$ 的整数序列 $a$ ,满足每个元素的因子个数不超过 $7$ .
你需要选出一个最短的非空子序列,使得子序列内元素乘积是平方数,输出这个长度,或判断无解.
$1\le n\le 10^5,1\le a_i\le 10^6$ .
由 $\sigma_0(a_i)\le 7$ 可以推出 $\omega(a_i)\le 2$ .
将 $a_i$ 质因数分解,次数是偶数的质因子没有贡献,可以直接忽略.
若还剩两个质因子 $x,y$ ,则在 $x,y$ 之间连边,若还剩 $1$ 个质因子 $x$ ,则在 $1,x$ 之间连边,若没有剩下,说明答案为 $1$ .
那么就得到了一张由 $1$ 和所有质数为结点的无向图,这张图上每一个环都对应了一个合法方案,只需要找出最小环.
枚举 $s$ 作为环的起点进行 bfs, 若某条边 $(x,y)$ 满足 $x,y$ 都被访问过,就有个长度为 $dis(x)+dis(y)+1$ 的环.
再优化一下,不难发现一个环一定包含了 $\le \sqrt {\max a_i}$ 的数,只枚举它们作为起点 bfs 即可.
时间复杂度 $O(n\sqrt {\max a_i})$ .
code
1043F Make It One
给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ,需要选出一个非空子集,使得集合内的数 $\gcd$ 为 $1$ ,输出最少选多少个数.
$1\le n,a_i\le 3\times 10^5$ .
记 $t(x)$ 表示有几个数是 $x$ 的倍数,记 $dp(i,j)$ 表示选 $i$ 个数使得它们的 $\gcd$ 为 $j$ 的方案数,转移有
$$
dp(i,j)=\binom{t(j)}{i}-\sum_{k\ge 2} dp(i,j\cdot k)
$$
对于每个 $i$ ,计算出所有 $dp(i,j)$ 需要 $O(n\log n)$ 的时间,但特判掉无解的情况后,答案显然不会太大.
考虑集合中开始只有一个数,加入新的数时,一定要让 $\gcd$ 的某个质因子次数减到 $0$ 才有用,否则可以不加入它.
于是可以得出当有解时,答案不会超过 $\omega(a)+1$ ,只用在这个范围内枚举 $i$ 即可,时间复杂度 $O(\omega(a)\cdot n\log n)$ .
code
367E Sereja and Intervals
给定 $n,m,x$ ,要构造出一个长度为 $n$ 的序列,每个元素是一个 $1\le l\le r\le m$ 的区间,需要满足没有区间完全包含另一个区间,且至少有一个区间的左端点为 $x$ ,求合法方案数,答案对 $10^9+7$ 取模, $1\le n\times m\le 10^5$ .
区间之间不能相互包含,则肯定没有两个区间是完全相同的,可以先不考虑顺序,求出方案数后乘上 $n!$ .
依次考虑 $1$ 到 $m$ 的每个数,每个数显然最多作为一次左端点,最多作为一次右端点,设 $dp(i,j,k)$ 表示考虑了前 $i$ 个数,还有 $j$ 个左端点未被匹配,已经匹配了 $k$ 个区间,转移时枚举这个数是否作为左右端点,是否和之前的端点匹配,因为区间不能有包含关系,所以若与之前剩下的端点匹配,方案是唯一的.当考虑到 $x$ 时,强制让它作为左端点即可.
时间复杂度 $O(n^2m)$ ,当 $n>m$ 时显然无解,所以复杂度为 $O(nm\sqrt {nm})$ ,可以通过.
code
710F String Set Queries
维护一个字符串集合 $S$ ,支持加入一个未加入过的串,删除一个已加入过的串,每次查询给出一个串 $s$ ,问集合 $S$ 中的串在串 $s$ 中出现了多少次,一个串在多个位置出现则计算多次,强制在线.
操作总数 $m\le 3\times 10^5$ ,修改,询问的字符串总长不超过 $3\times 10^5$ .
贡献是有可减性的,我们分别算加入的字符串贡献与删除的字符串贡献,将两者相减即可,只需要支持插入和询问.
如果可以离线,可以用 cdq 分治.
每次考虑左边插入对右边询问的贡献,对左边插入的串建出 AC 自动机,将右边的串放上去匹配.
现在强制在线,可以考虑二进制分组,维护 $O(\log m)$ 个 AC 自动机,插入串时新建一个自动机,并不断将最后的两个自动机合并,直到最后的两个自动机大小不同,询问时就在所有的 AC 自动机上都问一遍就可以了.
code
364D Ghd
给出一个大小为 $n$ 的可重集合 $S$ ,定义它的某个非空子集 $T$ 的权值为 $T$ 内所有元素的 $\gcd$ ,需要求出大小不小于 $n$ 的一半的所有子集的最大权值. $1\le n\le 10^6$ ,元素大小 $1\le a_i\le 10^{12}$ .
考虑每次随机一个数 $a_x$ ,计算包含它的,大小为 $\frac n 2$ 的集合最大的 $\gcd$ 是多少,那么做一次能得到正确答案的概率至少为 $\frac 1 2$ ,随机 $k$ 次,错误率就只有 $2^{-k}$ 了.
把所有 $a_i$ 与 $x$ 取 $\gcd$ 得到 $b_i=\gcd(a_i,x)$ ,那么枚举 $d$ 作为答案,如果 $d$ 的所有约数在 $b_i$ 中出现次数达到了 $\frac n 2$ ,就说明 $d$ 合法.实现时可以将所有 $b_i$ 存在一个 map 中,枚举 map 中的元素 $d,d’$ ,若 $d|d’$ ,就将 $d’$ 出现次数统计上.
时间复杂度 $O(k\cdot \sigma_0^2(a))$ ,可以适当进行剪枝.
code
1270G Subset with Zero Sum
给出一个长度为 $n$ 的序列 $a$ ,每个元素都满足 $i-n\le a_i\le i-1$ ,需要选出一个非空子序列,满足子序列中所有元素之和为 $0$ ,输出任意一种方案即可, $1\le n\le 10^6$ .
移项得到 $1\le i-a_i\le n$ ,每个点 $i$ 向 $i-a_i$ 连一条边,在图中随便找一个环,环上的点权值之和显然为 $0$ .
每个点都有出度,不可能是 DAG ,于是一定能找到一个环.
code
739E Gosha is hunting
有 $n$ 个小精灵,你有 $a$ 个普通球和 $b$ 个超级球,用普通球抓住第 $i$ 只小精灵的概率为 $A_i$，用超级球抓住第 $i$ 只小精灵的概率为 $B_i$ .
需要一开始就决定向哪些精灵投掷哪些精灵球,同种的球只能对一个精灵用一次,可以对一只精灵投掷两种球,如果两次中有一次抓到则视为抓到.询问当采用最优的方案时,最终抓到小精灵的期望个数是多少.
要求相对误差或绝对误差不超过 $10^{-4}$, $n\le 2000$ .
朴素的 dp 是设 $dp(i,j,k)$ 表示考虑了前 $i$ 个精灵,用了 $j$ 个普通球, $k$ 个超级球能获得的最大收益,是 $O(n^3)$ 的.
不难发现这个 dp 关于 $j,k$ 都是凸的,因为多用一个同种的球增加的收益肯定是递减的.
可以 WQS 二分,若只对其中一维进行二分,时间复杂度 $O(n^2\log \epsilon)$ ,对两维都二分可以做到 $O(n\log^2 \epsilon)$ .
code
526F Pudding Monsters
给定 $n$ 以及一个 $n\times n$ 的矩阵,每行每列恰好有一个位置是 $1$ ,其余地方是 $0$ ,只读入 $n$ 个 $1$ 的位置.
要从这个矩阵中找出一个 $k\times k$ 的子矩阵 ( $k$ 自选) ,满足子矩阵中 $1$ 的个数恰好是 $k$ ,求合法的方案数.
$n\le 3\times 10^5$ .
记第 $i$ 行的 $1$ 出现在第 $p_i$ 列,不难发现所有 $p_i$ 形成了一个排列,且方案数就是值域连续的区间的数目.
考虑枚举合法区间的右端点 $r$ ,合法的左端点需要满足 $\max[l,r]-\min[l,r]=r-l$ .
其中 $\max[l,r],\min[l,r]$ 分别表示区间 $[l,r]$ 内 $p_i$ 的最小值和最大值.
用线段树维护每个 $l$ 的 $\max[l,r]-\min[l,r]+l$ ,当右端点移动时,通过单调栈可以求出 $\max,\min$ 被修改的若干段区间,给这些区间各自整体加上改变量.
由于 $p$ 是排列,所以有 $\max[l,r]-\min[l,r]\ge r-l$ ,即 $\max[l,r]-\min[l,r]+l\ge r$ ,只需要在线段树上维护区间最小值以及最小值数目,就可以求得满足 $\max[l,r]-\min[l,r]+l=r$ 的 $l$ 的数目.
时间复杂度 $O(n\log n)$ .
code
338D GCD Table
给出 $n,m$ ,表示有一个 $n\times m$ 的矩阵,其中第 $i$ 行第 $j$ 列的元素是 $\gcd(i,j)$ ,读入一个长度为 $k$ 的序列 $a$ ,
判断这个序列是否在这个矩阵中作为某一行的一个连续段出现过, $1\le n,m\le 10^{12},1\le k\le 10^4$ .
经典题,假定序列 $a$ 是在第 $x$ 行第 $y$ 列开始出现的,那么 $x$ 必须是所有 $a_i$ 的倍数,即, $x$ 是所有 $a_i$ 的 $\rm lcm$ 的倍数.
记 $M={\rm lcm}(a_1,a_2,a_3,\dots,a_n),x=k\times M$ ,那么 $a_i=\gcd(k\times M, y+i-1)$ ,要求 $\frac {(y+i-1)}{a_i}\perp \frac M {a_i}\cdot k$ .
那么显然直接取 $k=1$ 是最优的,这样更有可能找到合法的 $y$ .
注意到 $a_i=\gcd(k\times M, y+i-1)$ ,说明 $a_i|y+i-1$ ,化成同余方程可以得到 $y\equiv 1-i\pmod {a_i}$ .
用 excrt 算法合并这些同余方程,得到一个 $y$ 的最小正整数解 $y_0$ ,那么 $y$ 一定是 $p\cdot M+y_0$ 的形式,由于对于每个 $i$ 都要满足 $\frac {(y+i-1)}{a_i}\perp \frac M {a_i}\cdot k$ ,直接让 $y=y_0$ 就是最优的,验证一下是否都成立即可,时间复杂度 $O(k\log n)$ .
code
839E Mother of Dragons
给出一张 $n$ 个点的无重边无自环无向图和一个正整数 $k$ ,你需要为每个点分配一个非负实数权值 $a_i$ ,满足 $k=\sum a_i$ .图中每条边 $(u,v)$ 会产生一个收益 $a_u\cdot a_v$ ,求总收益的最大值.
$1\le n\le 40,1\le k\le 1000$ ,要求相对误差或绝对误差在 $10^{-6}$ 以内.
首先通过大胆猜想等办法可以搞出一个高论:找出一个最大团,把权值平均分在这些点上是最优的.
证明大概可以考虑改变分配方式后一定不会变优,严格一点的证明过程可以参考 官方题解 .
于是只用求最大团的大小,可以用 $O(3^{\frac n 3})$ 的 BronKerbosch 算法,也可以 meet in the middle $O(n\cdot 2^{\frac n 2})$ 来做.
还有一个随机做法,每次随机一个排列 $p$ ,对每个点依次判断能否加入当前团中,若能,就贪心将其加入,多做几次.
code
960G Bandit Blues
给定 $n,A,B$ ,求有多少个长度为 $n$ 的排列,满足其前缀最大值恰有 $A$ 个,后缀最大值恰有 $B$ 个.
$1\le n\le 10^5,0\le A,B\le n$ ,答案对 $998244353$ 取模.
网上大多都是用第一类斯特林数求解的题解,这里分享另外一种思路比较简洁的做法.
考虑将 $[1,n]$ 内的数从大到小插入到当前排列中,第一个数比较特殊,它同时是前后缀的 $\max$ .
而对于后面插入的数,若之前排列中已有 $i$ 个数,那么让它成为前缀 $\max$ 和后缀 $\max$ 的方案都是 $1$ 种,其余 $i-1$ 种方案既不是前缀 $\max$ ,也不是后缀 $\max$ .
于是将第一个数的贡献单独计算,不难得出答案为 $[x^{A-1}y^{B-1}]\prod_{i=1}^{n-1}(x+y+i-1)$ .
可以把 $\prod_{i=1}^{n-1}(x+y+i-1)$ 看作一个关于 $x+y$ 的多项式,求出其各项系数后用二项式定理简单计算答案即可.
用分治 NTT ,时间复杂度 $O(n\log^2 n)$ ,若用 倍增 NTT ,可以做到与第一类斯特林数做法相同的复杂度 $O(n\log n)$ .
其实第一类斯特林数做法的式子展开后和这个东西是一样的,只不过感觉这个做法推起来比较直接.
1285F Classical?
给出一个长度为 $n$ 的正整数数列 $a$ ,求出 $\max_{i\neq j} {\rm lcm}(a_i,a_j)$ , $2\le n\le 10^5,1\le a_i\le 10^5$ .
将每个 $a_i$ 的因子 $d$ 也都加入数列 $a$ 中,于是问题变为在数列 $a$ 中求两个互质的数的最大乘积.
将所有 $a$ 从大到小排序,依次枚举 $x=a_i$ ,若存在 $y>x,y\perp x$ ,那么区间 $(x,y)$ 内的数与 $x$ 就没有贡献了.维护一个栈来存储所有可能与 $x$ 产生贡献的 $y$ ,那么枚举到 $x$ 时,就不断弹栈并计算贡献,直到栈内没有与 $x$ 互质的数.
对每个 $x$ 维护栈内有多少个数与 $x$ 互质,可以维护 $f(d)=\sum_{d|y} cnt(y)$ ,则与 $x$ 互质的数个数为 $\sum_{d|x}\mu(d)f(d)$ .
实现时可以直接用计数排序,时间复杂度 $O(n+a\log a)$ .
code
1295F Good Contest
有一个长度为 $n$ 的序列 $a$ ,其中 $a_i$ 是区间 $[l_i,r_i]$ 内等概率随机选取的整数,问序列 $a$ 单调不升的概率.
答案对 $998244353$ 取模, $1\le n\le 50,0\le l_i\le r_i<998244353$ .
直接划艇即可.
先对所有端点离散化并排序,设 $dp(i,j)$ 表示考虑了前 $i$ 个数,第 $i$ 个数在最后 $ j$ 个区间中的方案数.
转移时考虑枚举 $k$ ,表示第 $i-k+1$ 到第 $i$ 个数都在第 $j$ 个区间中,前面的数都不在第 $j$ 个区间中.
$$
dp(i,j)=dp(i,j-1)+\sum_{k=1}^{i} dp(i-k,j-1)\cdot\binom{len_j+k-1}{k}
$$
其中 $len_j$ 表示从后往前第 $j$ 个区间的长度,时间复杂度 $O(n^3)$ .
code
961G Partitions
给出一个长度为 $n$ 的序列 $w$ 以及一个正整数 $k$ ,需要将 $1$ 到 $n$ 这 $n$ 个整数划分成恰好 $k$ 个集合,定义一个集合 $S$ 的权值为 $|S|\cdot \sum_{i\in S}w_i$ ,一个划分的权值为分出的所有集合权值之和,求所有合法划分的权值总和.
$1\le k\le n\le 2\times 10^5$ ,答案对 $10^9+7$ 取模.
一个划分的权值可以这样考虑,若 $u,v$ 被划分到了同一个集合中,则对划分的权值产生 $w_u+w_v$ 的贡献, $u=v$ 也算.
那么计算所有划分的权值之和时,直接考虑每对 $u,v$ 的贡献即可.
$$
ans=(\sum w_i)\cdot{n\brace k}+\sum_{u\neq v} (w_u+w_v)\cdot {n-1\brace k}\\
ans=(\sum w_i)\cdot ({n\brace k}+(n-1){n-1\brace k})
$$
这里只用算两个第二类斯特林数,直接展开暴力算即可,时间复杂度 $O(n+k\log n)$ .
code
722E Research Rover
有一个 $n\times m$ 的网格图,初始在左上角 $(1,1)$ ,随机沿着一条最短路径走到右下角 $(n,m)$ ,初始有个权值 $s$ ,图上有 $k$ 个关键点,每经过一个关键点,当前的权值 $x$ 就会变成 $\lceil \frac x 2\rceil$ ,询问到终点时权值的期望.
$1\le n,m,s\le 10^5,0\le k\le 2000$ ,答案对 $10^9+7$ 取模.
将 $(1,1), (n,m)$ 也视作关键点,最后对答案简单处理即可.
设 $dp(i,j)$ 表示走到了第 $i$ 个关键点,经过了至少 $j$ 个关键点的方案数.显然第二维只用开到 $\log s$ .
转移时考虑枚举经过了 $j-1$ 个关键点时走到了 $k$ ,有 $dp(i,j)=\sum (dp(k,j-1)-dp(k,j))\cdot |{\rm Path}(k\to i)|$ .
其中 $|{\rm Path}(k\to i)|$ 表示从第 $k$ 个关键点到第 $i$ 个关键点的方案数,时间复杂度 $O(n+m+k^2\log s)$ .
code
995F Cowmpany Cowmpensation
给出一个 $n$ 个点的有根树,为每个点分配一个 $[1,D]$ 内的正整数作为权值,需要满足每个点的权值不大于其父亲的权值,求合法的方案数, $1\le n\le 3000,1\le D\le 10^9$ ,答案对 $10^9+7$ 取模.
答案是关于 $D$ 的 $n$ 次多项式,可以考虑归纳证明.
当 $n=1$ 时显然成立,否则我们记各个子树大小分别为 $a_1,a_2\dots a_k$ , 枚举根的权值为 $i$ ,得到方案数为
$$
\sum_{i=1}^D\prod_{j=1}^k f(a_j,i)
$$
根据我们的归纳假设,可知 $f(a,x)$ 是一个关于 $x$ 的 $a$ 次多项式,因为 $\sum a_j=n-1$ ,那么每个 $\prod_{j=1}^k f(a_j,i)$ 都是关于 $i$ 的 $n-1$ 次多项式,于是方案数可以写成 $\sum_{k=0}^{n-1}c_k \sum_{i=1}^D i^k$ 的形式,这显然是关于 $D$ 的 $n$ 次多项式.
于是只需要暴力 dp 出 $D=1,2,\dots,n-1$ 时的答案,然后做拉格朗日插值即可,时间复杂度 $O(n^2)$ .
code
283E Cow Tennis Tournament
有一张 $n$ 个点的竞赛图,初始时每条边都由编号较大的指向编号较小的,有 $k$ 次操作,每次操作给出 $[l,r]$ ,表示对于所有 $u,v\in[l,r],u\neq v$ ,翻转边 $(u,v)$ 的方向.问所有操作结束后图中三元环的数目. $3\le n\le 10^5,1\le k\le 10^5$ .
竞赛图的三元环个数是经典问题了,补集转化可知答案为 $\binom n 3-\sum_{i=1}^n \binom{outdeg_i}{2}$ ,其中 $outdeg_i$ 表示 $i$ 的出度.
于是只需要求出最后每个点的出度,考虑将所有操作按照 $l$ 排序,从左往右依次计算每个位置 $i$ 的答案,先将 $l\le i$ 的翻转操作全部执行,将 $r=i-1$ 的翻转操作全部撤销,然后询问 $<i$ 的位置有多少个数被翻转了偶数次, $>i$ 的位置有多少个数翻转了奇数次,相加即为 $i$ 的出度,不难发现修改和询问可以用线段树支持,时间复杂度 $O(n\log n)$ .
code