Miscellaneous
Codeforces 1119F - Niyaz and Small Degrees
对于一个固定的度数限制 \(x\)，显然有 dp：\(f(u,0/1)\) 表示考虑 \(u\) 以及子树内的点边，是否删除了 \(u\) 连向 \(father_u\) 的边，这时满足限制的最小删边权值和为多少。
假设所有点的度数都大于等于 \(x\)，那么 \(f(u,0)\) 的转移应该是先假定所有儿子 \(v\) 都是 \(f(v,0)\)，之后再选出若干 \(v\) 加上 \(f(v,1)-f(v,0)\)，表示删除这些点，保证删完之后 \(u\) 是满足限制的。
对于度数小于等于 \(x\) 的点，可以挂在父亲上，和 \(f(v,1)-f(v,0)\) 一起算。这个可以使用平衡树做到。
但是对于 \(x\in [0,n-1]\) 我们都要计算答案，是否会超时呢？实际上并不会，用的时间应该是 \(O\sum_{x\in[0,n-1]}\sum_{1\le i\le n} [d_i\ge x])=O(\sum d)=O(n)\)。
所以总的时间复杂度为 \(O(n\log_2 n)\)。
Submission #276341229 - Codeforces
[CCC2019] Tourism
发现显然有如果要让游览到第 \(n\) 个景点的天数最少，那么第 \(i\) 天游览完前 \(p_i\) 个景点，那么一定有游览到第 \(p_i\) 个景区的最少天数为 \(i\)，这样我们将原本的 \(n\) 个景点分成了 \(\lceil\frac{n}{k} \rceil\) 段，每段有且仅有一天可以游览到这其中的景点。于是就可以 \(O(n)\) 的转移了。
QOJ #2568. Mountains
记 \(f(i,j)\) 表示在矩阵 \(A\) 上从 \((1,1)\) 走到 \((i,j)\) 的路径元素和最大值。那么发现有 \(f\) 与 \(A\) 构成双射，那么需要统计 \(f\) 的个数。显然 \(f\) 中的所有值都在 \([0,k]\) 中。
而且根据 \(f\) 的转移可知，\(f(i,j)\le x\) 的 \((i,j)\) 一定是从 \((1,1)\) 开始阶梯状排列的，只需要统计在 \(n\times m\) 的矩阵中插入 \(k\) 条轮廓线的方案数即可。这个可以将每条轮廓线向左下平移，转化成求 \(k\) 个起点和终点要求一一对应，每个起点各自到各自的终点的路径之间互不相交的方案数。然后使用 LGV 引理即可。
QOJ #3082. Ascending Matrix
与上题类似，\(a_{r,c}=v\) 的限制可以使用多项式插值解决。
「ZJOI2022」树
\(f(i,x,y)\) 表示考虑到第 \(i\) 个位置时钦定 \([1,i]\) 中有 \(x\) 个属于 \(T_1\) 的非叶子节点，\([i+1,n]\) 中有 \(y\) 个属于 \(T_2\) 的非叶子节点，这时的方案数。
从 \(i\) 转移到 \(i+1\) 时可以考虑钦定 \(i+1\) 的身份：
钦定 \(i+1\) 是 \(T_1\) 的叶子节点： \(f(i+1,x,y-1)\leftarrow f(i,x,y)\times x\times (y - 1)\)。
钦定 \(i+1\) 是 \(T_2\) 的叶子节点：\(f(i+1,x+1,y)\leftarrow f(i,x,y)\times x\times y\)。
初始化：\(f(1,1,i)=i\)。
求答案：\(F_n=\sum_i f(n-1,i,1)\times i\)。
那么有一个问题是有可能出现 \(\exists i\) 既是 \(T_1\) 的叶子也是 \(T_2\) 的叶子，这种情况会算两遍，因此额外加入一个容斥转移 \(f(i+1,x,y)\leftarrow f(i,x,y)\times x\times y\)。
时间复杂度 \(O(n^3)\)。
提交记录 #2135370 - LibreOJ (loj.ac)
「AHOI2022」山河重整
可以发现一点是，如果要求 \(S\sube \{1,2,\cdots, n\}\) 能够满足可以使用子集元素的和表出 \(1,2,\cdots,n\)，那么充要条件是：
\[\forall i\le n:i\le \sum_{v\in S,v\le i}v \]证明有很多种，可以简单归纳，或者更简单地通过 \(O(n^2)\) 的 dp 推得。
更进一步，如果有 \(S\) 不满足上述条件，则 \(S\) 第一个不能表出的数应该是最小的 \(i\) 使得 \(i> \sum_{v\in S,v\le i} v\)，此时得出 \(S\) 中 \(< i\) 的数一定只能连续表出到 \(i-1\)。
记 \(f(i)\) 表示使用 \(\le i\) 的数，和为 \(i\) 且能表出 \([1,i]\) 中的所有数字的方案个数。那么应该有 \(answer=2^n-\sum_{i=0}^{n-1} 2^{n-i-1} f(i)\)。
剩下就是求出 \(f(i)\) 了。
注意到 \(f(i)\) 实际上就是要求满足上述条件的互异分拆数，那么我们记 \(h(i)\) 表示互异分拆数，那么一定会有 \(f(i)=h(i)-g(i)\)，其中 \(g(i)\) 表示不满足上述条件的互异分拆数。根据容斥容易得出 \(g(i)=\sum_{j=0}^{i-1} f(j) \cdot t(i-j,j+2)\)，其中 \(t(u,v)\) 表示用大于等于 \(v\) 的各个不同的数字拼出 \(u\) 的方案数。容易发现只有 \(j\le \frac{i}{2}\) 的时候 \(t(i-j,j+2)\) 才可能有值，因此可以类似半在线卷积地根据 \(f(0),\cdots ,f(\lfloor\frac{n}{2}\rfloor)\) 直接求出 \(f(\lfloor\frac{n}{2}\rfloor + 1),\cdots,f(n)\) 的值，递归下去就可以了。
提一句 \(h\) 的计算是类似于 \(O(n\sqrt n)\) 求分拆数的 dp，而 \(g\) 的计算可以类似 \(h\) 的计算，因为如果 \(t(i-j,j+2)\) 选出了 \(k\) 个数，那么可以每个数减去 \((j+2)\)，总共减去 \((j+2)k\) 之后再求出这 \(k\) 个数的和为 \(i-j-(j+2)k\) 的方案数，我们可以用求 \(h\) 的方法加上精妙的改动后用来求 \(g\)，具体可见代码。
时间复杂度 \(T(n)=O(n\sqrt n) + T(n/2)=O(n\sqrt n)\)。
提交记录 #2135608 - LibreOJ (loj.ac)
「2021 集训队互测」这是一道集训队胡策题
妙妙妙计数题，这两个月遇到的计数题让我以为我自己根本不会计数。
考虑如果 \(\sum_{i,j} ([a_i=c_{i,j}]+[b_j=c_{i,j}]-[a_i=b_j])=n^2\) 那么一定满足条件。而且显然有 \(\sum_{i,j} ([a_i=c_{i,j}]+[b_j=c_{i,j}]-[a_i=b_j])\le n^2\)。因此只要让这个式子尽量去取到最大值即可。发现 \(\sum_{i,j}[a_i=b_j]=(\sum_{i} a_i)(\sum_{j} b_j)+(n-\sum_{i} a_i)(n-\sum_{j} b_j)\)，那么就可以将 \(a\) 和 \(b\) 分离单独处理。
对于每个 \(x=\sum_{i} a_i\)，计算出最大的 \(\sum_{i,j}[a_i=c_{i,j}]\)，并算出有多少种方案可以得出这个最大值。\(y=\sum_j b_j\) 同理。
然后枚举 \(x,y\) 计算即可。单独计算是 \(O(n)\)，但枚举 \(x,y\) 的时间复杂度是 \(O(n^2)\)，所以总的时间复杂度为 \(O(n^2)\)。
提交记录 #2135864 - LibreOJ (loj.ac)
「2020-2021 集训队作业」Tour
部分分：\(a_i\ge 0\)。
记 \(c_i=a_{p_i}\)，原条件相当于 \(\forall i< n:c_ic_{i+1}\le w\)。
将 \(a\) 按从小到大的顺序排序，显然这不会影响答案。同时建立一个队列 \(q\)，执行以下操作直到 \(a\) 被删空：
- 记 \(x\) 为当前 \(a\) 中最小的数，\(y\) 为 \(a\) 中最大的数。
- 如果 \(xy\le w\)，则在 \(a\) 中弹出 \(x\) 并在 \(q\) 的末尾加入 \(x\)，并将 \(x\) 标记为好的；如果 \(xy>w\)，则在 \(a\) 中弹出 \(y\) 并在 \(q\) 的末尾加入 \(y\)，并将 \(y\) 标记为坏的。
然后可以按照队列内部的顺序依次将队内元素插入 \(c\) 中，因为无论什么插入顺序只要满足题目要求就可以计数。这时有一个看似显然实则非常非常强大的性质，就是如果当前队首元素为 \(x\)，当 \(x\) 为好的时，当前队中的所有元素与 \(x\) 的乘积一定都 \(\le w\)；当 \(x\) 为坏的时，当前队中的所有元素与 \(x\) 乘积一定都 \(>x\)。
那么我们在插入时可以记录当前空位数，初始时只有一个空位，此时考虑要插入 \(x\)：
- 如果 \(x\) 为好的，那么将 \(x\) 插入任意一个空位之后都会有：它的左右两边在之后都可以插入新的数，而它本身消耗了一个空位数，所以空位数会增加一个。
- 如果 \(x\) 为坏的，那么将 \(x\) 插入任意一个空位之后都会有：它的左右两边在之后都不能插入新的数，而它本身消耗了一个空位数，所以空位数会减少一个。
而插入时任意空位显然是等价的，因此考虑记录空位数即可。
具体的，如果队中第 \(i\) 个元素为好的，则 \(t_i=1\)；否则 \(t_i=-1\)。那么答案就是：
\[\prod_{i=1}^n(1+\sum_{j=1}^{i-1}t_j) \]主要用到了两个关键（但是显然）的性质：
- 任意插入顺序对答案没有影响。
- 任意数字集合 \(S\)，总是存在 \(v\) 使得它和 \(S\) 中任意数的乘积都同时 \(\le w\) 或者 \(>w\)。换句话说，对于是否满足题目的要求，一定存在一个数使得后续的插入均满足或均不满足。
部分分：\(n\le 2000\)。
不妨把 \(0\) 当作正数考虑。
显然一正一负是满足限制的。
因此可以按正负分段，设正数极长连续段个数为 \(i\)，负数极长连续段个数为 \(j\)，应该有 \(|i-j|\le 1\)，这样就做到了正负分离，只需要分别计算正数 \(i\) 段的方案数和负数 \(j\) 段的方案数并乘起来即可。
记 \(F(i)\) 表示正数的极长连续段个数为 \(i\) 时的方案数（负数同理）。我们希望求出这个，但是很困难。一个想法是将上个部分分的初始一个空位改成 \(i\) 个。这样计算出的实际上是至多 \(i\) 个连续段的方案数记为 \(f(i)\)，且如果恰有 \(x\) 个极长连续段，则这种方案会在 \(f(i)\) 中被计算 \({i\choose x}\) 次。
那么就有二项式反演： \(f(i)=\sum_{j\le i} {i\choose j} F(j)\Rightarrow F(i)=\sum_{j\le i} (-1)^{i+j}{i\choose j} f(j)\)。
可以 \(O(n^2)\) 求出 \(F\) 和 \(f\)。然后同理求出负数的 \(G\) 和 \(g\)，然后枚举 \(f,g\) 来 \(O(n)\) 合并。
如果想要做到可过的时间复杂度，就需要一些多项式科技了。
首先可以知道 \(f(x) = \prod_{i=1}^n(x+\sum_{j=1}^{i-1}t_j)=\prod_{i=1}^n (x+s_i)\)，这个可以分治求出，然后多点求值求出 \(f(0),f(1),\cdots,f(n)\) 的值。
发现：
\[\begin{aligned} F(x)=&\sum_{i=0}^{\infty} (-1)^{x+i}{x\choose i} f(i) \\ =&(-1)^x\sum_{i=0}^{\infty} (-1)^{i}\frac{x^{\underline i}}{i!} f(i) \end{aligned} \]可以得出 \(\mod x^{n+1}\) 意义下的 \(F(x)\) 的下降幂多项式的系数，因为此时是下降幂多项式，因此多点求值是好做的。
但是到此为止了吗？
继续观察，发现难写的地方是对于 \(f(x)\) 多点求值，但是如果 \(f(x)\) 是下降幂多项式形式就会很简单，因此我们直接在分治卷积的时候就把 \((x+s_i)\) 当作下降幂多项式，这样进行下降幂多项式乘法就可以快速求出 \(f(0),\cdots,f(n)\) 的值了。
当然常数还是很大，所以我对 \(a_i\ge 0\) 的包进行了单独判断才过了。如果写 4-base 的 NTT 会快很多。
提交记录 #2136325 - LibreOJ (loj.ac)
标签：空位,le,08,times,2024,插入,做做,可以,sum From： https://www.cnblogs.com/imcaigou/p/18363639