模考.md
2022-12-31
2022 的我最后一天。
T1
题意是啥？考虑有多少个区间的和是 \(2^i\) 并且每个位置的数是 \(2^k\)。
考虑这样，如果 \(a_i\) 是最大值的话，那么最后的答案只可能是 \(a_i,a_i+1,\cdots a_i+\log n\) 这 \(\log n\) 种答案。
直接分治，然后每次计算最大值在这边（左/右）的答案，另外一边指针移动。然后我们每次查询 \(\log n\) 个值，那么直接进行哈希查询即可。
复杂度是 \(n\log^2 n\)。
T2
对于每一个 \(k\) 计算 \(\sum_{i=1}^n\binom{a_i+b_i-k}{a_i}\)
那么写出生成函数
\[ \begin{aligned} \binom{a_i+b_i-k}{a_i}&=\binom{a_i+b_i-(n-k)}{a_i}\\ &=[x^{b_i-n+k}]\frac{1}{(1-x)^{a_i+1}}=[x^k]\frac{x^{n-b_i}}{(1-x)^{a_i+1}} \end{aligned} \]
发现实际上要计算的是若干个 \(\frac{f(x)}{(1-x)^a}\) 的和。
如果 \(f(x)\) 都是低次多项式，那么我们可以在 \(n\log^2 n\) 的复杂度算出答案。
我们按 \(a\) 从大到小排序。每 \(B\) 个多项式算一次。
\(G(x)=(F(x)+H_i(x))\frac{1}{(1-x)^{B}}\)
现在我们只需要的快速计算 \(H_i(x)\)。
考虑 \(H_i(x)=\sum_{i}f_i(x)(1-x)^{B-i}\) 这类的，我们一次多项式乘法复杂度是 \(O(Bq)\)，然后 \(\sum q=n\) 这样总复杂度自然是 \(O(Bn)\)。
乘一次 \(\frac{1}{(1-x)^B}\) 的复杂度自然是 \(n\log n\)，我们总共需要计算 \(n/B\) 次，所以复杂度就是 \(O(Bn+n/B*n\log n)\)。
可能给我的启示就是多项式其实也可以分块算这样的？
T3
题意，对于每一个排列 \(p(n)\) 计算，最大权匹配。
\(e(i,j)=\max_{k=i}^{j-1}(p_k)\)。
我们考虑如果给我们一个图，我想计算他的最大权匹配，怎么计算？
如果当前的最大值是 \(p_i\)，那么我们一定要尽可能让匹配经过 \(p_i\)，也就是我们呢一定会产出 \(\min(i,n-i)\) 个。接下来确实变成了子问题。
那么我们什么时候会停止呢？我们建立出笛卡尔树，每次如果子树大小 \(\le n/2\) 那么一定会停止。因为如果我们至少可以让子树内匹配子树外。
也就是说我们只会让子树 \(x\ge n/2\) 的节点产生贡献。
我们考虑 \(a_i\) 的子树大小为 \(j\) 的的笛卡尔树（排列生成的）个数。
记 \(g(j)\) 表示大小为 \(j\) 的子树能产生答案的总和。
\[ g(j)=\sum_{i=0}^{j-1} \min(\min(i+1,j-i),j-n/2) \]
最后的 \(j-n/2\) 的含义是，外面有 \((n+1-(j+1))\)，内部最多产生 \(\frac{(j+1)-(n+1-(j+1))}{2}=j-[n/2]\)。
考虑如何生成的一颗笛卡尔树。我们从大向小一一插入，这样我们只需要每次插入在叶子的位置就是合法的。
可以对于大小为 \(x\) 的笛卡尔树，一定有 \(x+1\) 个可以插入的位置。
记 \(f(n)=n!\) 为大小为 \(n\) 的排列数，我们写出来答案：
\[ \begin{aligned} [f(i-1)\times i]\times [f(j-1)\times g(j)\times \binom{n}{j-1}]\times (i-1)\times (i)\times (i+1)\times \cdots \end{aligned} \]
第一部分是说我们大于 \(a_i\) 的 \(i-1\) 个数可以任意选择，然后我们选择一次 \(i\) 把这大小为 \(j\) 的子树发到这个位置，接下来剩下的数都可以任意插入。
考虑能这样做的一个原因是 \(\ge n/2\) 的节点必定会形成一条链。
然后发现最后可以写成卷积形式。就好了。
2022-12-28
T1
简要题意，给定一个网格，起初每个位置都有无限多的水，我们可以进行 \(k\) 次吸水。每次吸水会把所有能到达这个位置的水吸走，问每次剩余水的最小值。
这个问题我也觉得很迷惑呀，真心感觉“吸水”这个定义很诡异。
如果是一维的情况，那么最高的位置上面的水一定会全部消失。然后左右变成子问题，而另一个区间就完全无关了。
我们考虑实际上是每次删去一个区间的全部贡献这样的，那么可以建出笛卡尔树，设置好对应的权值，每次操作相当于覆盖一条到根的链。这个问题可以用长链剖分解决。（原因是我们必定选长链（反证然后调整），接下来变成子问题）
那么二维情况也是类似的。如果我们删除当前最高后，连通性未改变的话，这个相当于递归到了只有一种情况的子问题。就删点，判联通。反着做变成了加点判联通，妥妥的并查集。
我不是很懂。
T2
简要题意：定义一个 \(n\times m\) 的01矩阵合法，当且仅当不存在另外一个矩阵他们的一行一列1的个数都相等。
考虑如果存在一对1 \((a,b),(c,d)\)，若可以进行交换 \((a,d),(c,b)\)。
我们按列进行考虑，记每一列的状态是 \(s_i\),如果存在 \(s_i\not\subset s_j,s_j\not \subset s_i\) 的情况，那么必定可以交换。
我们按 \(|s_i|\) 排序后一定会得到，\(s_i\subset s_{i+1}\)。
对于一个排好序的 \(|s_i|\) 序列，答案是：
\[ \prod \binom{n-s_{i-1}}{s_i-s_{i-1}}=\prod \frac{(n-s_{i-1})!}{(n-s_i)!(s_i-s_{i-1})!}=n! \prod \frac{1}{(s_i-s_{i-1})!} \]
那么我们有多少种序列呢？
当然 \(n!\prod \frac{1}{d_i!}\)。
如果记 \(f_i\) 表示分成 \(i\) 段序列的个数，\(g_i\) 表示分成 \(i\) 段上述答案。
那么总答案就是 \(\sum f_i\times g_i\)。
\[ \begin{aligned} f_i&=[x^n](e^x-1)^i=[x^n]\sum_{k=0}^i \binom{i}{k}(-1)^{i-k}e^{kx}\\ &=i!\sum_{k}\frac{(-1)^{i-k}}{(i-k)!}\frac{k^n}{k!} \end{aligned} \]
ntt。
\(g\) 与 \(f\) 不同的就只有他多了两项（首项，尾项）可以为0的。
\(g_i=[x^n](e^x-1)^{i-1}(e^x)^2\) 类似卷积即可。
T3......
(解方程？主元个数有限。)
1-2
两个菜题都不太想写sol。
（那么cage,cage为什么还没有都切掉的？那答案只能是cage也菜呀！）
T1
题意，定义一个排列进行如下操作，从前往后枚举元素，随意放前/后，生成的序列为可到达的。给你 \(n\) 个长度 \(m\) 的排列，问他们共同可到达的排列个数，以及字典序最小的。
很简单，考虑最后一个位置，如果相同，那么我可以任意放前/后，否则我们就有两种数，这样是对称的。
我们发现接下来的决策是固定的。所以可以直接往下推，直到他们匹配的位置再次对齐。
这样还是子问题。递归解决。
T2
题意：给你 \(2(n-1)\) 个数，分别表示点的父亲，点到父亲边的权值。问你对于所有的 \(k\) 点 \(1\) 到点 \(n\) 间有 \(k\) 条边的最大路径权。
考虑我们选出来 \(k\) 个递增的点在什么情况不合法，当然是除去他们构不成树的情况。
所以问题变成如何判断点集能构成树，这个当且仅当 \(\sum [a_i\le k]\ge k\)。
因为 \(2,\cdots k+1\) 的父亲都小于等于 \(k\)。
然后我们发现我们删除一些点几乎所有点都会因为有一个 \(1\) 被删除，而限制变紧1。除了 \(a_{k+1}\) 被删除的，他们限制保持不变（因为多减去一个 \(k+1\) 抵消）。
所以如果最开始就有不合法的，那么一定全无解。
否则我们可以通过选择 \(k+1\) 让 \(k\) 合法。
所以贪心策略是，我们先选择所有的 \(\sum [a_i\le k]= k\) 的，然后从小向大选择，发现这个过程是单调的，所以直接做就是 \(O(n)+O(n\log n)\) 的，似乎可以直接桶排，就没有 \(\log n\) 了。