officeyutong

$$ \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