$$ \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
阅读全文..

考虑$p\neq 0$的情况。

使用$a_i$表示数字i出现的次数。

构建一棵线段树,令$a_i$覆盖$[i-a_i+1,a_i]$的区间,最终$[1,n]$内为0的位置的个数即为答案。

很显然一个位置为0,我们必定要调整之后的某个数到这个位置来覆盖它。

带整体加减?

区间平移。

#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
阅读全文..

大量的细节+自己不熟悉AC自动机。

  1. 基于DFS的记忆化搜索是错的,转移顺序有问题。
  2. 走到了一个点,即代表这个点在失配树上到根的所有点都匹配到了,所以要把他们加起来。
  3. DP各种东西好好想想,别眼瞎。
  4. 分清楚这步转移时从哪到哪的

原题的式子取个log,变成了经典的取若干个东西使得他们的平均值最大的问题,01分数规划即可。

给每个串加上一个附加权,然后AC自动机跑DP,最大化权值即可。

#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
阅读全文..