/px

被卡读入,自毙。

按照下标分块,令块大小为$N$,则对于每一组询问$(x,y)$,当$x\geq N$时直接暴力枚举所有符合要求的点$xk+y$(不会超过$N$个);

对于$x<N$的情况,我们维护一个二维数组$arr[x][y]$,表示$arr[x][y]$的答案,回答时直接输出即可。

对于修改操作,我们直接枚举所有不超过$N$的数,分别取模后修改数组即可。

#include
阅读全文..

$$ \text{对于矩阵}M,\text{构造其特征多项式}G\left( x \right) \\ \text{则有}M^n=G\left( M \right) Q\left( M \right) +R\left( M \right) \\ \text{即}M^n\equiv R\left( M \right) \left( mod\,\,G\left( M \right) \right) \\ \text{即}x^n\equiv R\left( x \right) \left( \text{mod }G\left( x \right) \right) \\ \text{考虑特征多项式如何计算。} \\ G\left( x \right) =\det \left( M-x\text{I} \right) ,\text{其中}I\text{为单位矩阵} \\ \text{由于}G\left( x \right) \text{为}n\text{次多项式}\left( n\text{为矩阵大小} \right) ,\text{故可以通过插值求出来对应的特征多项式。} \\
\\ \text{然后多项式快速幂}+\text{取模即可} $$

#include
阅读全文..

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