这是一个 $k + 1$ 维偏序问题，如果使用 CDQ 分治的话将收获 $\mathcal O(n\log^k n)$ 的复杂度，而 $n = 40000$ 的情况下 $\log^k n$ 在这题已经是 $10^6$ 的量级，甚至跑不过暴力 $\mathcal O(n^2k)$。

考虑 bitset，我们用 $S_i$ 的一个 bitset 存储当前所有维度均小于 $i$ 的节点，每次对新的维度排序，然后 bitset and 一下即可。不难发现这样可以正确维护。

时间复杂度 $\mathcal O(\frac{n^2k}{\omega})$，其中 $\omega$ 是计算机位数，一般取 $\omega = 32\ \mathrm{or}\ 64$，跑得飞快，比一些实现的不好的 KDTree 正解还要快。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int Hen_hen_eaaaaa(233333);struct Eat{ int Now,Nxt,Bef,Col;}eat[Hen_hen_eaaaaa],frt[Hen_hen_eaaaaa];int n,cnt,STT;bool NOW;inline int R(){ int x=0,f=1;char c='c'; while(c>'9'||c<'0'){f=f*(c=='-'?-1:1);c=getchar();} while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();} return x*f;}int main(){ freopen("csp2021pj_fruit.in","r",stdin); freopen("csp2021pj_fruit.out","w",stdout); n=R(); if(!n) return 0; for(int i=1;i<=n;++i){frt[i].Col=R();frt[i].Bef=i-1;frt[i-1].Nxt=i;} NOW=!frt[1].Col;frt[0].Nxt=1; for(int i=1;i<=n;++i){ if(frt[i].Col!=NOW){ NOW=frt[i].Col; eat[++cnt].Now=i; eat[cnt].Bef=cnt-1; eat[cnt-1].Nxt=cnt; } } int N,NN,NNN; while(frt[0].Nxt&&eat[0].Nxt){ N=eat[0].Nxt; while(N){ printf("%d ",eat[N].Now); NN=eat[N].Now; frt[frt[NN].Bef].Nxt=frt[NN].Nxt; frt[frt[NN].Nxt].Bef=frt[NN].Bef; eat[N].Now=frt[NN].Nxt; NNN=eat[N].Now; if(((frt[NNN].Col!=frt[NN].Col)||(!NNN))&&((frt[eat[eat[N].Bef].Now].Col!=frt[NN].Col)||(!eat[N].Bef))){ eat[eat[N].Bef].Nxt=(eat[N].Bef?((eat[eat[N].Nxt].Nxt&&eat[N].Nxt)?eat[eat[N].Nxt].Nxt:0):eat[N].Nxt); eat[eat[eat[N].Nxt].Nxt].Bef=((eat[N].Bef&&eat[eat[N].Nxt].Nxt&&eat[N].Nxt)?eat[N].Bef:eat[eat[eat[N].Nxt].Nxt].Bef); eat[eat[N].Nxt].Bef=((eat[N].Bef||!eat[N].Nxt)?eat[eat[N].Nxt].Bef:0); } N=eat[N].Nxt; } printf("\n"); } return 0;}

nfls 集训的作业题。

考虑 dp。设 $f_i$ 表示前 $i$ 个串的最小代价，$s_i$ 为前缀和，则：

$$f_i=\min_{j\in [0,i)} f_j+|s_i-s_j+i-j-L-1|^p$$

然后发现右边的东西关于 $s_i+i-L-1$ 是一个对称的东西，而且二阶导恒非负。这个时候考虑使用二分队列优化决策单调性。

考虑用三元组 $\left\langle j, l, r \right\rangle$ 表示 $l\to r$ 内的最优决策点为 $j$。

遍历 $i:1\to n$，当队首的 $r\lt i$ 的时候先扔掉，然后令 $l=i$。

对于队尾的一些 $\left\langle j,l,r \right\rangle$，如果 $i\to l$ 的决策比 $j\to l$ 的决策更优，根据决策单调性，$[l,r]$ 内的决策都是 $i$ 更优，直接舍弃 $j$，更替为 $i$。

如果我们弹出的过程中遇到了第一个不满足上述条件的 $\left\langle j,l,r \right\rangle$，那么一定存在一个决策点 $p\in [l,r]$，满足 $\forall x\in [l,p]$，$j$ 更优，$\forall x\in [p+1,r]$，$i$ 更优。直接二分出来就行。

时间复杂度均摊 $\mathcal O(n\log n)$。

COGS 为啥不支持 LaTeX 的 \binom，只能用 $\mathrm C$ 表示组合数了。

非常暴力的组合数计数。

考虑拆贡献，对 $i$ 节点，我们枚举 $k = sz_i$，计算 $i$ 子树大小为 $k$ 的方案数，然后直接暴力乘起来。

$i$ 子树内的方案数是 $$(k - 1)!\times \mathrm C_{n - i}^{k - 1}$$

表示 $\gt i$ 的树中选 $k - 1$ 个进行排列，然后 $i$ 子树外的方案数是 $i!\times (i + 1 - 2)\times (i + 2 - 2)\dots \times (n - k + 1 - 2) = i\times (i - 1)\times (n - k - 1)!$。

那么 $i$ 的方案数就是 $$\sum_{k=1}^{n-i+1} k\times (n - k)\times (k - 1)!\times \mathrm C_{n - i}^{k - 1}\times i\times (i-1) \times (n - k - 1)!$$

谔谔，为什么会RE，我干啥了，别的地方都能AC啊。

首先设 $f_i$ 为 $i$ 个点的 DAG 数量，枚举其中的 $i-j$ 个点没有入度，然后剩下 $j$ 个点向它们随意连边，但这样会算重，需要在容斥一下，方程是：

$$ f_i = \sum_{j=1}^{i}{(-1)^{j-1} C_i^j 2^{j(i-j)} f_{i-j}}$$

时间复杂度 $O(n^2)$，可过 $n=5000$。

这个式子看起来就很能卷积，不过这个 $2^{j(i-j)}$ 很烦，可以化一下：

$$j(i-j)=\frac{i^2}{2}-\frac{j^2}{2}-\frac{(i-j)^2}{2}$$

这样就能把 $j$ 和 $i-j$ 分开了。于是：

$$ f_i = \sum_{j=1}^{i}{(-1)^{j-1} \frac{i!}{j!(i-j)!} 2^{\frac{i^2}{2}-\frac{j^2}{2}-\frac{(i-j)^2}{2}} f_{i-j}}$$

$$   = 2^{\frac{i^2}{2}}i! \sum_{j=1}^{i}{\frac{(-1)^{j-1}}{2^{\frac{j^2}{2}}j!} \frac{f_{i-j}}{2^{\frac{(i-j)^2}{2}}(i-j)!} }$$

设:

$$A(x)=\sum_{i \ge 1}{\frac{(-1)^{i-1}}{2^{\frac{i^2}{2}}i!}x^i}$$

$$F(x)=\sum_{i \ge 0}{\frac{f_i}{2^{\frac{i^2}{2}}i!}x^i}$$

于是：

$$F = A*F +1$$

即：

$$F = \frac{1}{1-A}$$

使用 FFT 卷积，时间复杂度 $O(n\log(n))$，可过 $n=100000$。

做法一：

首先设 $f_i$ 表示至少 $i$ 对和睦的方案，$g_i$ 表示恰好 $i$ 对和睦的方案。

显然有：

$$f_i=\sum_{j=i}^{n}{C^i_jg_j}$$

根据二项式反演，有：

$$g_i=\sum_{j=i}^{n}{(-1)^{j-i}C^i_jf_j}$$

而我们还有：

$$f_i=C^i_nA^i_n2^i(2n-2i)!$$

于是：

$$g_i=\sum_{j=i}^{n}{(-1)^{j-i}C^i_jC^j_nA^j_n2^j(2n-2j)!}$$

$$=\frac{n!^2}{i!}\sum_{j=i}^{n}{\frac{(-1)^{j-i}2^j}{(j-i)!(n-j)!}}$$

显然可以卷积，于是时间复杂度 $O(Tn\log n)$.

本题还有个加强版，每次询问只需要求一组 $(n,k)$ 的答案，但 $T \le 2e5,n \le 5e6$。

做法二：

发现实际要求的是错排的方案数，记 $F_n$ 表示 $n$ 对情侣的错排方案数，于是：

$$ans(n,k)=C^k_nA^k_n2^kF_{n-k}=(C^k_n)^2k!2^kF_{n-k}$$

而显然：

$$\sum_{k=0}^{n}{ans(n,k)}=\sum_{k=0}^{n}{(C^k_n)^2k!2^kF_{n-k}}=(2n)!$$

化成卷积形式：

$$\sum_{k=0}^{n}{\frac{2^k}{k!}\frac{F_{n-k}}{(n-k)!^2}}=\frac{(2n)!}{n!^2}$$

于是我们设:

$$A(x)=\sum_{i \ge 0}{\frac{2^i}{i!}x^i}$$

有：

$$A(x)=\sum_{i \ge 0}{\frac{(2x)^i}{i!}}=e^{2x}$$

再设：

$$F(x)=\sum_{i \ge 0}{\frac{F_i}{i!^2}x^i}$$

再设：

$$B(x)=\sum_{i \ge 0}{\frac{(2i)!}{i!^2}x^i}$$

根据广义二项式定理，有：

$$B(x)=(1-4x)^{-\frac{1}{2}}$$

再代入上边的卷积式得：

$$A \cdot F=B$$

也就是：

$$F(x)=\frac{e^{-2x}}{(1-4x)^{\frac{1}{2}}}$$

求个导：

$$F'(x)=\frac{8xe^{-2x}}{(1-4x)^{\frac{3}{2}}}=\frac{8x}{1-4x}F(x)$$

于是得到：

$$F'(x)=4xF'(x)+8xF(x)$$

观察系数：

$$F_{n+1}=4n(n+1)F_n+8n^2(n+1)F_{n-1}$$

终于得到了递推式，可以 $O(n+T)$ 解决加强版。本题同样也可 $O(n+Tn)$。