原题等价于，反转 01 串的一段后缀，使得 01 串的 popcnt 最小。

证明：因为没有子串 10，最后一定是 00000...11111 。

于是把原串分为左右两段：

• 左边一段删去所有的 1，操作次数即 popcnt。
• 右边一段删去所有的 0，操作次数即反串的 popcnt。

注意到反转后缀对 popcnt 的增减量是后缀和（0 为 1，1 为 -1），

考虑增量构造，设 $r$ 为当前情况下原串的 popcnt，$m$ 为当前情况下的答案。

• 若往后添加一个 $1$（概率 $1-p_n$），$m$ 不变，$r++$。
• 若往后添加一个 $0$（概率 $p_n$），
  • 如果 $r=m,r,m$ 均不变。（不反转是最优的）
  • 否则 $r$ 不变，$m++$。（反转会多产生 $1$ 的代价）

于是设 $l=r-m$，则设 $f_{n,l,m}$ 即可得到 $\Theta(n^3)$ 的 dp。

注意到期望满足线性性，于是设 $f_{n,l}$ 表示期望，$g_{n,l}$ 表示概率，即可得到 $\Theta(n^2)$ 的 dp：

$$f_{0,0}=0,g_{0,0}=1$$ $$f_{n,l}=p_n(f_{n-1,l+1}+g_{n-1,l+1})+(1-p_n)f_{n-1,l-1}\quad(l\not=0)$$ $$g_{n,l}=p_ng_{n-1,l+1}+(1-p_n)g_{n-1,l-1}\quad(l\not=0)$$ $$f_{n,0}=p_n(f_{n-1,0}+f_{n-1,1}+g_{n-1,1})$$ $$g_{n,0}=p_n(g_{n-1,0}+g_{n-1,1})$$

接下来考虑怎么多项式搞这玩意。

这玩意很毒瘤，不是倍增也不是分治，而是倍僧套分治。。。

显然往末尾填 $p_n=0$ 对最终答案没有影响，把 $n$ 填充为 $2$ 的幂次。

注意到 $l\le n$，因此 dp 状态相当于一个等腰直角三角形

显然这玩意适合倍增

于是我们只要考虑如下直角梯形的转移

卷积允许我们作如下等腰梯形的转移

于是把梯形分成左右两段，上面就可以卷积转移

下面的转移可以分治

于是直角梯形的转移就可以分治 FFT $\Theta(n\log^2 n)$ 解决。

等腰直角三角形的转移就倍增套上直角梯形的转移就行了，

总复杂度 $T(n)=T\left(\dfrac{n}{2}\right)+\Theta(n\log^2 n)=\Theta(n\log^2 n)$

首先题解中给出结论：

最后一个条件不成立，当且仅当能将 $S_1,S_2,\cdots,S_m$ 划分为两组 $L,R$，使得 $\displaystyle\max_{a\in S,S\in L}a<\min_{a\in S,S\in R}a$ 。

证明题解中有，就略去了。

在此基础上，考虑容斥，设 $f_{n,m}$ 为答案，$g_{n,m}=\displaystyle{ n\brace m}$，则

$$g_{n,m}\sum_k\sum_{\small\sum_{i=1}^ka_i=n\atop\sum_{i=1}^nb_i=m}f_{i,j}$$

即，将 $1,2,\cdots,n$ 任意划分为 $m$ 个无标号非空集合，等价于将 $m$ 个集合划分为 $k$ 组 $T_1,T_2,\cdots,T_k$，使得 $\forall i\in[1,k),\displaystyle\max_{a\in S,S\in T_i}a<\min_{a\in S,S\in T_{i+1}}a$ 。

显然该式可用二元生成函数表示

$$g(x,y)=\dfrac{1}{1-f(x,y)}$$

$$f(x,y)=1-\dfrac{1}{g(x,y)}$$

$\Theta(nm)$ 预处理出第二类斯特林数后，$\Theta(n^2\log n)$ 二维 FFT + 多项式求逆即可。

因为要任意模数 NTT，所以跑的还没 $\Theta(n^3)$ 快，希望出题人下次给个 NTT 模数。。。

题意

给定一 $k$ 维位线性空间，需要找出向量序列 $\vec{a}_1,\vec{a}_2,\cdots,\vec{a}_n$，

使之张成的线性子空间维度为 $t$，且子空间中不包含 $\vec{X}$。

$\forall t\in[1,k]$，求方案数。

题解

首先特判 $\vec{X}=\vec{0}$ 的情况：此时等价于 $\vec{a}_1,\vec{a}_2,\cdots,\vec{a}_n$ 线性无关。

对于 $\vec{a}_1,\vec{a}_2,\cdots,\vec{a_i}$，其张成的线性子空间维度为 $i$，包含 $2^i$ 个向量。

$\vec{a}_{i+1}$ 不能是这 $2^i$ 个向量中的任意一个，因此答案即

$$\prod_{i=0}^{n-1}(2^k-2^i)$$

接下来考虑 $\vec{X}\not=\vec{0}$ 的情况，显然答案和 $\vec{X}$ 具体是什么无关。

同样考虑逐步添加向量，设当前线性子空间 $V$ 的维度为 $i$。

• 若添加下一个向量后 $V$ 维度不变，则下一个向量在 $V$ 中，
  有 $|V|-1=2^i-1$ 种可能。
• 否则，由于 $\vec{X}\notin V$，设 $W=V\cup\{\vec{a}+\vec{X}|\vec{a}\in V\}$，
  则下一个向量一定不在 $W$ 中，否则就会表出 $\vec{X}$ 或使维度不增加，
  有 $2^k-|W|=2^k-2^{i+1}$ 种可能。

总上，因为加入了 $n$ 个向量，最终维度为 $t$，
有 $t$ 次加入使维度增加，其余 $n-t$ 次加入使维度不变，答案即

$$\left(\prod_{i=0}^{t-1}(2^k-2^{i+1})\right)\sum_{\sum_{i=1}^tb_i=n-t}\prod_{i=1}^t(2^i-1)^{b_i}$$ $$=[x^{n-t}]\prod_{i=1}^t\dfrac{2^k-2^i}{1-(2^i-1)x}$$

$n$ 很大，但分母是已因式分解的多项式，考虑线性递推

$$[x^n]\dfrac{1}{1-ax}=a^n$$ $$[x^n]\dfrac{1}{(1-ax)(1-bx)}=\sum_{k=0}^na^kb^{n-k}=b^n\sum_{k=0}^n\left(\dfrac{a}{b}\right)^k$$ $$=b^n\dfrac{\left(\dfrac{a}{b}\right)^{n+1}-1}{\left(\dfrac{a}{b}\right)-1}=\dfrac{a^{n+1}}{a-b}+\dfrac{b^{n+1}}{b-a}$$

由于求和满足线性性，归纳可得

$$[x^n]\prod_{1\le i

因此答案的通项为

$$[n\ge t]\left(\prod_{i=1}^t(2^k-2^i)\right)\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle\prod_{\small j\not=i\atop1\le j\le t}(2^i-2^j)}$$

显然 $\displaystyle\left(\prod_{i=1}^t(2^k-2^i)\right)$ 可以 $\Theta(n)$ 递推。于是设

$$f_t=\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle\prod_{\small j\not=i\atop1\le j\le t}(2^i-2^j)}\qquad(t\le n)$$

将下面的 $\prod$ 拆开

$$f_t=\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle\left(\prod_{j=1}^{i-1}(2^i-2^j)\right)\left(\prod_{j=i+1}^t (2^i-2^j)\right)}$$

将 $2^i$ 从 $\prod$ 中提出来

$$f_t=\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle2^{i(t-1)}\left(\prod_{j=1}^{i-1}(1-2^{j-i})\right)\left(\prod_{j=i+1}^t (1-2^{j-i})\right)}$$

$$f_t=\sum_{i=1}^t\dfrac{2^{-i(t-1)}(2^i-1)^{n-1}}{\displaystyle\left(\prod_{j=1}^{i-1}(1-2^{-j})\right)\left(\prod_{j=1}^{t-i} (1-2^{j})\right)}$$

分母已经是卷积形式了，套路性的拆开 $2^{-i(t-1)}$

$$-i(t-1)=\dbinom{t-i}{2}-\dbinom{t}{2}-\dbinom{i}{2}$$

$$f_t=2^{\binom{t-i}{2}}\sum_{i=1}^t\dfrac{2^{-\binom{i}{2}}(2^i-1)^{n-1}}{\displaystyle\prod_{j=1}^{i-1}(1-2^{-j})}\times\dfrac{2^{\binom{t-i}{2}}}{\displaystyle\prod_{j=1}^{t-i}(1-2^j)}$$

NTT $\Theta(n\log n)$ 卷积即可。即

$$a_i=\dfrac{(2^i-1)^{n-1}}{\displaystyle\prod_{j=1}^{i-1}(1-2^{-j})},b_i=\dfrac{1}{\displaystyle\prod_{j=1}^i(1-2^j)},c_i=2^{\binom{i}{2}}$$

$$f_t=c_t\sum_{i=1}^t(a_ic_i^{-1})(b_{n-i}c_{n-i})$$

$$ans=\displaystyle\mathop{\operatorname{xor}}\limits_{t=1}^{\min(k,n)}\left(f_t\prod_{i=1}^t(2^k-2^i)\right)$$

预处理 $a_i,b_i,c_i$ 有轻微卡常注意。

首先改坐标：$a\leftarrow a-1,b\leftarrow b-1$。

设 $g_{k,y}$ 为导弹和坦克走到 $(k,y)$ 并相遇的方案数，$f_{k,y}$ 为导弹和坦克走到 $(k,y)$ 并第一次相遇的方案数。则

$$g_{k,y}=\dbinom{2k+a}{k,k,a}\dbinom{a}{y}=\sum_{i=0}^kf_{k-i,y}\dbinom{2i}{i}$$

设 $h(x)=\displaystyle\sum_{k=0}^\infty\dbinom{2k}{k}x^k$，则

$$\dbinom{2(k+1)}{k+1}=\dfrac{(2k+2)^{\underline{2}}}{(k+1)^2}\dbinom{2k}{k}=\left(4-\dfrac{2}{k+1}\right)\dbinom{2k}{k}$$

$$h(x)=4xh(x)-2\int h(x)\mathrm{d}x+1$$

$$h'(x)=4xh'(x)+4h(x)-2h(x)$$ $$\dfrac{h'(x)}{h(x)}=\dfrac{2}{1-4x}$$ $$h(0)=1,h(x)=Ce^{\int\frac{2\mathrm{d}x}{1-4x}}=\dfrac{1}{\sqrt{1-4x}}$$

设 $f_y(x)=\displaystyle\sum_{k=0}^\infty f_{k,y}x^k,g_y(x)=\displaystyle\sum_{k=0}^\infty g_{k,y}x^k$，则

$$g_y(x)=\dfrac{f_y(x)}{\sqrt{1-4x}}$$

$$f_y(x)=\sqrt{1-4x}g_y(x)$$

于是答案即

$$\sum_{y=0}^a\sum_{k=0}^bf_{k,y}f_{b-k,y}$$ $$=\sum_{y=0}^a[x^b]f^2_y(x)$$ $$=\sum_{y=0}^a[x^b](1-4x)g_y^2(x)$$ $$=\sum_{y=0}^a\dbinom{a}{y}^2[x^b](1-4x)g_0^2(x)$$ $$=\dbinom{2a}{a}[x^b](1-4x)g_0^2(x)$$

$\Theta(a+b)$ 计算阶乘和卷积即可。

对 #887 的求解促使我们研究更一般的情况

$$f_{n+1}=af_n^2+bf_n+c\qquad(a\not=0)$$

这一递推统称为二次非线性递推。

显然，我们可以用同样的方法分离变量

$$\left(af_{n+1}+\dfrac{b}{2}\right)=\left(af_{n+1}+\dfrac{b}{2}\right)^2+ac+\dfrac{b}{2}-\dfrac{b^2}{4}$$

因此，我们只要考虑一种情况

$$f_{n+1}=f_n^2+c$$

它就是 Pollad-rho 中所用到的随机函数。

• $c=0$ 时，显然有通项公式 $f_n=f_0^{2^n}$。

• $c\not=0$ 时，该数列是具有 混沌性 的，这意味着我们求不出一般的通项公式。 但我们可以渐进估计它。我们有

  $$f_n\sim C^{2^n}\qquad(n\rightarrow\infty)$$

  $C$ 是某个常数。

因此，考场上遇到它，套路是分离变量，如果 $c\not=0$ 就算了吧（

这题可以出到 $d_i\le 32000$，但仁慈的出题人并没有那么做。

正解是常系数齐次线性递推。这玩意有 $5$ 种解法：

• 暴力递推 $\Theta(k\max d_i)$
• 矩阵快速幂 $\Theta((\max d_i)^3\log k)$
• 特征方程 $\Theta(\log k),d\le 5$
• 多项式求逆 $\Theta(k\log k)$
• 多项式取模 $\Theta((\max d_i)\log(\max d_i)\log k)$

显然具体方法可以为矩阵快速幂或多项式取模。

简述下题意：

有一个可重集，有顺序地选若干次，每次从中选一个数，使最终的和 $\le k$，求方案数。

显然可以转化为生成函数：

设 $[x^m]g(x)$ 为和恰好为 $m$ 的方案数，$f(x)=\displaystyle\sum_ix^{d_i}$，

则 $g(x)=\displaystyle\sum_{i=0}^\infty f^i(x)=\dfrac{1}{1-f(x)}$

因为要求 $\le k$，做一遍前缀和——答案就是

$$\dfrac{[x^k]}{(1-x)(1-f(x))}$$

本题的 $k$ 很大，根据常系数齐次线性递推的一般理论，

设 $f^R(x)$ 为 $(1-x)(1-f(x))$ 翻转的结果，则我们只需要求出

$$x^k\bmod f^R(x)$$

多项式取模即可解决这个问题。

或者矩阵快速幂：矩阵下面放递推系数，上面斜着放 $1$。

对于这一题，我们有 $\Theta((k\log k+\log m)\log n)$ 的做法。

对于 $i\in[1,n]$，显然当且仅当 $x\in(i-\mathrm{lowbit}(i),i]$ 时，

$v$ 会对 $c_i$ 产生贡献。

设 $\mathrm{cnt}_i=\displaystyle\sum_{j=1}^n[\mathrm{lowbit}(j)=i]$，显然 $\mathrm{cnt}_i=\left\lfloor\dfrac{n-i}{2i}\right\rfloor+1\quad(i\le n)$

因此答案即为

$$\sum_i\dfrac{\mathrm{cnt}_i}{n^m}\sum_{j=0}^m\dbinom{m}{j}i^j(n-i)^{m-j}(S+1)^{-j}\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\left(\sum_{u=1}^ja_u\right)^k$$

• $\dfrac{1}{n^m}\dbinom{m}{j}i^j(n-i)^{m-j}$ 表示 $m$ 次中有 $j$ 次产生了贡献。
• $\displaystyle (S+1)^{-j}\sum_{a_1,a_2,\cdots a_j\in[0,S]}\left(\sum_{u=1}^ja_u\right)^k$ 表示枚举贡献。

右边的 $k$ 次方不好搞，转为牛顿级数：

$$\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\left(\sum_{u=1}^ja_u\right)^k=\sum_{r=0}^k{k\brace r}r!\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\dbinom{a_1+a_2+\cdots+a_j}{r}$$

此时可以范特蒙德卷积

$$\dbinom{a_1+a_2+\cdots+a_j}{r}=\sum_{\sum_{u=1}^jb_u=r}\prod_{u=1}^j\dbinom{a_u}{b_u}$$

调换枚举顺序，发现可以上指标求和

$$\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\dbinom{a_1+a_2+\cdots+a_j}{r}=\sum_{\sum_{u=1}^jb_u=r}\prod_{u=1}^j\sum_{a_u=0}^S\dbinom{a_u}{b_u}$$

$$=\sum_{\sum_{u=1}^jb_u=r}\prod_{u=1}^j\dbinom{S+1}{b_u+1}$$

因此设 $f(x)=\displaystyle\sum_{v=0}^{\infty}\dbinom{S+1}{v+1}x^v$，则

$$\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\dbinom{a_1+a_2+\cdots+a_j}{r}=[x^r]f^j(x)$$

于是最终的答案就是

$$\sum_i\dfrac{\mathrm{cnt}_i}{n^m}\sum_{r=0}^k{k\brace r}r![x^r]\sum_{j=0}^m\dbinom{m}{j}i^j(n-i)^{m-j}(S+1)^{-j}f^j(x)$$

$$=\sum_i\dfrac{\mathrm{cnt}_i}{n^m}\sum_{r=0}^k{k\brace r}r![x^r]\left(\dfrac{if(x)}{S+1}+n-i\right)^m$$

$[x^r]\left(\dfrac{if(x)}{S+1}+n-i\right)^m$ 多项式快速幂即可 $\Theta(k\log k+\log m)$。

因此最终复杂度为 $\Theta((k\log k+\log m)\log n)$。

当然如果不想写任意模数 NTT 的话 $\Theta(k^2\log n\log m)$ 也可以...

我们可以无脑得到答案就是

$$\sum_{2a+2b+c+d=n}\dbinom{n}{2a,2b,c,d}$$

直接 EGF 套上去

$$n![x^n]{\left(\sum_{k}\dfrac{x^k}{k!}[2|k]\right)}^2{\left(\sum_k\dfrac{x^k}{k!}\right)}^2$$

右边显然是 $e^{2x}$。

左边 $[2|k]$ 直接单位根反演：$[2|k]=\dfrac{(-1)^k+1}{2}$

因此左边就是 $(\dfrac{1}{2}(e^x+e^{-x}))^2$，随便算一下，答案就是

$$n![x^n]\dfrac{1}{4}(e^{4x}+2e^{2x}+1)$$

$$=4^{n-1}+2^{n-1}+\dfrac{1}{4}[n=0]$$

右边 $\dfrac{1}{4}[n=0]$ 不要，左边高精度快速幂即可。

复杂度 $\Theta(n^2\log n)$，若使用 FFT 的话复杂度 $\Theta(n\log^2 n)$

zjy 总是说“dp 意义下山没有区别”啥的，重申一下，他说的是：

$$f(S)=f_{|S|}$$

意思是答案只和集合的大小有关。

而一般说的“有区别”，是等价类意义下的。

对于两座山 1 和 2，1 夏 2 冬 和 1 冬 2 夏 是两种不同的方案。

如果我们认为它们是相同的，那么我们要计算的是：

$$\sum_{2a+2b+c+d=n}1=[x^n]\dfrac{1}{(1-x^2)^2}\dfrac{1}{(1-x)^2}$$

这玩意我们可以有限微积分做，推柿子极其痛苦，答案是

$$\dfrac{1}{48}(2(n+4)^{\underline{3}}+3(n+3)((-1)^{n}-1))$$

设 $a_1+a_n=a_2+a_{n-1}=\dots=a_\frac{n}{2}+a_{\frac{n}{2}+1}=\bar{a}$，易得 $\displaystyle \bar{a}=\frac{2}{n}\sum^n_{i=1}a_i$
构造多项式 $\displaystyle\sum^\frac{n}{2}_{i=1}(\bar{a}-a_i-a_{n-i+1})^2=0$，若该式成立，则原题目条件成立，于是 $$\sum^\frac{n}{2}_{i=1}(\bar{a}^2-2\bar{a}(a_i+a_{n-i+1})+(a_i+a_{n-i+1})^2)=0$$ $$\sum^\frac{n}{2}_{i=1}(a_i+a_{n-i+1})^2=2\bar{a}\sum^n_{i=1}a_i-\frac{n}{2}\bar{a}^2$$ $$\sum^\frac{n}{2}_{i=1}(a_i^2+a_{n-i+1}^2+2a_ia_{n-i+1})=\frac{n}{2}\bar{a}^2$$ $$\frac{n}{2}\bar{a}^2-\sum^n_{i=1}a_i^2=2\sum^\frac{n}{2}_{i=1}a_ia_{n-i+1}=\sum^n_{i=1}a_ia_{n-i+1}$$ 最后有 $\displaystyle\frac{n}{2}\bar{a}^2-\sum^n_{i=1}a_i^2=\sum^n_{i=1}a_ia_{n-i+1}$，左边为 $\Theta(n)$ 计算，与顺序无关的定值。

右边为卷积的形式，$\Theta(n\log n)$ 全部算出来，一个一个与左边比对即可。

具体的，设 $f(x)=(\displaystyle\sum^{n-1}_{i=0}a_ix^i)^2,f_i$ 为其第 $i$ 项， 则滚动 $k$ 次右边的值为$f_{n-1+k}+f_{(2n-1+k)\bmod 2n}$