officeyutong

$$ \sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^ia_{i\text{mod}4}}=\sum_{0\le j\le 3}{a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left[ i\equiv j\left( mod\,\,4 \right) \right]}} \\ =\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left[ i-j\equiv 0\left( mod\,\,4 \right) \right]}\\ \end{array}} \\ \text{令}\omega _4\text{为模998244353意义下的四次单位根，则有}\sum_{0\le i<3}{\omega _{4}^{i}}=0 \\ \text{显然对于任意非零的}k,\text{有}\sum_{0\le i<3}{\omega _{4}^{ik}}=\text{0,而对于}k=\text{0则有}\sum_{0\le i<3}{\omega _{4}^{ik}}=4 \\ \text{故}\sum_{0\le j\le 3}{a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left[ i-j\equiv 0\left( mod\,\,4 \right) \right]}}=\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\frac{1}{4}\sum_{0\le k\le 3}{\omega _{4}^{k\left( i-j \right)}}}\\ \end{array}} \\ \text{当且仅当}i-j=0\left( \text{mod}4 \right) \text{时，有}\frac{1}{4}\sum_{0\le k\le 3}{\omega _{4}^{k\left( i-j \right)}}=1 \\ \sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\frac{1}{4}\sum_{0\le k\le 3}{\omega _{4}^{k\left( i-j \right)}}}\\ \end{array}}=\frac{1}{4}\sum_{0\le j\le 3}{a_j\sum_{0\le k\le 3}{\omega _{4}^{-kj}\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\omega _{4}^{ki}}}} \\ =\frac{1}{4}\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le k\le 3}{\omega _{4}^{-kj}\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left( \omega _{4}^{k} \right) ^i}}\\ \end{array}} \\ =\frac{1}{4}\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le k\le 3}{\omega _{4}^{-kj}\left( s\omega _{4}^{k}+1 \right) ^n}\\ \end{array}} \\ $$

#include

询问按照x从小到大分类。

然后按照x递增处理，每次把根到x的路径上深度为p的点的值加上$p^k-(p-1)^k$。

这样对于任何一条到根深度为p的路径，其权值为$p^k$。

使用树剖+线段树维护。

线段树的每个叶子节点有一个权值$p^k-(p-1)^k$，这个权值不会改变，同时需要维护区间$a_i\times(p_i^k-(p_i-1)^k)$的和。

#include

单调栈板子题..?

首先按位拆分，然后转变为统计一个01矩阵中所有全1的子矩阵（按位与）以及所有全0的子矩阵（用总矩阵数减掉即为按位或的答案）。

打表可知$n\times n$的矩阵有$(\frac{n(n+1)}2)^2$个子矩阵。

统计全1矩阵和全0矩阵本质一样，故我们先考虑统计全0矩阵。

考虑处理出来$f(i,j)$，表示如果第i行第j列的元素时0，那么往上到什么位置的元素也全都是0。对于是1的位置，$f(i,j)=-1$。

然后我们枚举一个下界$low$，表示现在我们要统计下边缘在$low$上的矩形个数。

然后从左到右扫，维护一个单调栈，单调栈内的元素是列，设$S_i$为栈中自底向上第$i$个元素，那么满足$f(low,i+1)>f(low,i)$。

先不考虑出栈，考虑入栈。

处理右下角为$(i,j)$时的答案时，设$x$表示合法的矩形数量

假设第i列的元素$i$入栈的时候，我们设$S_{-1}$表示栈内最后一个元素，$S_{-2}$以此类推。

如果加入元素i不会使得任何元素出栈，那么我们可以得到以$(i,j)$为右下角的所有合法的矩形数量为$x+f(low,i)$。

由于加入i不会导致元素出栈，故$f(low,i)$一定大于栈中其他元素的值，所以第i列较低的$S_{-1}$列可以和前面的拼起来，比$S_{-1}$高的部分可以自己成一个宽度为1的矩形。

如果导致了元素出栈呢？

左侧到$S_{-2}$，上边界到$f(low,S_{-1})$的矩形不可能再次被取到，减掉即可。

#include

$$ \text{设}f\left( n \right) \text{表示}2\times n\text{的矩形的方案数。} \\ \text{设}g\left( n \right) \text{为}2\times n,\text{全部使用}1\times \text{2的砖块填充的方案数} \\ \text{转移则有}f\left( n \right) =f\left( n-1 \right) +f\left( n-2 \right) +2\sum_{1\le j\le n-2}{g\left( j-1 \right)}\left( \text{枚举在第}j\text{列放置第一个}1\times \text{1的块，第}n\text{列放置第二个} \right) \\ =f\left( n-1 \right) +f\left( n-2 \right) +\sum_{0\le j\le n-3}{g\left( j \right)} \\ \text{由}g\left( 0 \right) =g\left( 1 \right) =\text{1,}g\left( n \right) =g\left( n-1 \right) +g\left( n-2 \right) \text{知}\sum_{0\le j\le n-3}{g\left( j \right)}=g\left( n-1 \right) -1 \\ \text{故}f\left( n \right) =f\left( n-1 \right) +f\left( n-2 \right) +2g\left( n-1 \right) -2 \\ \,\,\text{构造矩阵} \\ M_1=\left[ \begin{matrix}{l} f\left( 1 \right)& f\left( 2 \right)& g\left( 1 \right)& g\left( 2 \right)& -2\\ \end{matrix} \right] \text{和转移矩阵}T=\left[ \begin{matrix}{l} 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 2& 1& 1& 0\\ 0& 1& 0& 0& 1\\ \end{matrix} \right] \\ \text{则}M_1T^{n-1}\text{即为结果矩阵。} \\ f\left( 1 \right) =f\left( 2 \right) =\text{0,}g\left( 1 \right) =\text{1,}g\left( 2 \right) =2 \\ $$

#include

完了我已经掉成Pupil了..

考虑对于每次询问做一个DP处理。

设$f(i,j,k)$表示使得串1的前i位，串2的前j位，串2的前k位能在主串中同时不相交出现的最短的前缀长度。

设$g(n,ch)$表示第n个字符之后，ch第一次出现的位置，如果不存在则设为$\infty$。

转移时考虑$f(i,j,k)=min(g([i\geq 1]f(i-1,j,k),S_1(i)),g([j\geq 1]f(i,j-1,k),S_2(j)),g([k\geq 1]f(i,j,k-1),S_3(k)))$。

边界条件$f(0,0,0)=0$。

可是这样单组询问复杂度是$O(250^3)$的，尽管这也是个常数。

但是注意到每组询问要么是追加一个字符，要么是删除末尾的字符。

假设在第i个串后追加一个字符，那么只需要把第i个串的DP数组推进一维即可。

删除第i个串末尾的字符，只需要把DP数组其他两维置INF。

#include

强行把两道不相关的题合到一起？不过还好，毕竟可以出到任意二阶递推数列（三阶的其实也可以，只要有人会解三次方程）

$$ \text{考虑第一部分：} \\ \sum_{1\le i\le n}{G\left( i,k \right)}=\sum_{1\le i\le n}{\left( \begin{array}{c} F_i\\ k\\ \end{array} \right) =\frac{1}{k!}\sum_{1\le i\le n}{F_i^{\underline{k}}}},\text{其中}F_i\text{为斐波那契数列,}F_0=\text{1,}F_1=1 \\ =\frac{1}{k!}\sum_{1\le i\le n}{\prod_{0\le j<k}{\left( F_i-i \right)}} \\ \text{构造}k\text{次多项式}H\left( x \right) =\prod_{0\le j<k}{\left( x-j \right)}=\sum_{0\le i\le k}{h_ix^i} \\ \text{则有}\sum_{1\le i\le n}{G\left( i,k \right)}=\frac{1}{k!}\sum_{1\le i\le n}{\sum_{0\le j\le k}{h_jF_{i}^{j}}} \\ =\frac{1}{k!}\sum_{0\le j\le k}{h_j\sum_{1\le i\le n}{F_{i}^{j}}} \\ \text{设}f\left( n,k \right) =\sum_{1\le i\le n}{F_{i}^{k}} \\ \text{由}F_i=\frac{5+\sqrt{5}}{10}\left( \frac{1+\sqrt{5}}{2} \right) ^n+\frac{5-\sqrt{5}}{10}\left( \frac{1-\sqrt{5}}{2} \right) ^n,\text{设}a=\frac{5+\sqrt{5}}{10},b=\frac{5-\sqrt{5}}{10} \\ x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2} \\ \text{则}F_i=ax_{1}^{n}+bx_{2}^{n} \\ \text{构造模意义下的数域}a+b\sqrt{5} \\ \text{则有}f\left( n,k \right) =\sum_{1\le i\le n}{F_{i}^{k}}=\sum_{1\le i\le n}{\left( ax_{1}^{i}+bx_{2}^{i} \right) ^k}=\sum_{1\le i\le n}{\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jx_{1}^{ij}b^{k-j}x_{2}^{i\left( k-j \right)}}} \\ =\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jb^{k-j}\sum_{1\le i\le n}{x_{1}^{ij}x_{2}^{i\left( k-j \right)}}} \\ =\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jb^{k-j}\sum_{1\le i\le n}{\left( x_{1}^{j}x_{2}^{k-j} \right) ^i}}=\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jb^{k-j}\frac{\left( x_{1}^{j}x_{2}^{k-j} \right) ^{n+1}-1}{x_{1}^{j}x_{2}^{k-j}-1}} \\ \text{第二个求和号等比数列求和即可。} \\ \text{第一部分复杂度}O\left( k^2\log k \right) \\ \text{考虑第二部分。} \\ \text{设}f\left( n \right) \text{表示长度为}n\text{的答案，打表可知} \\ f\left( 2n \right) =4f\left( 2n-2 \right) -f\left( 2n-4 \right) \\ \text{只考虑取偶数的}2n,\text{则}f\left( n \right) =4f\left( n-1 \right) -f\left( n-2 \right) \text{。} \\ \text{计算特征根}x_1=2+\sqrt{3},x_2=2-\sqrt{3} \\ \text{设}f\left( n \right) =ax_{1}^{n}+bx_{2}^{n},\text{由}f\left( 0 \right) =\text{1,}f\left( 1 \right) =\text{3得} \\ a=\frac{3+\sqrt{3}}{6},b=\frac{3-\sqrt{3}}{6} \\ \text{仍然像第一部分一样处理即可。} \\ $$

#include