codechef Future of draughts

难度

super-hard

题意

官方中文题意

做法

定义1:\(G\)为邻接矩阵,\(I\)为单位矩阵
定义2:\(H\)为转移矩阵,可以不动,即\(H=G+I\)
定义3:\(e_i(x_1,...,x_n)\)为\((x_1,...,x_n)\)的所有\(i\)子集乘积和

\(i\)到\(j\)走\(K\)步的方案数即\(G^K_{ij}\),可以通过\(O(Tn^3K)\)算出来

但这样显然会超时

注意到我们只需要\(tr(H^N)\),对于加法矩阵的每个元素是线性无关的,试图从特征多项式入手

从关于\(H\)的特征值入手,设\(H\)的\(n\)个特征值为\(\lambda_1,...,\lambda_n\)
定理1:\(tr(H^N)=\sum\limits_{i=1}^n \lambda_i^N\)

证明:证明\(\lambda\)是\(H\)的特征向量,则\(\lambda^N=H^N\)的特征向量即可
\(x\in V^n\)非零向量,即\(Ax=\lambda x\)
下面即例\(N=2\)
有\(AAx=A(\lambda x)=\lambda(Ax)=\lambda^2x\)

定理2(牛顿恒等式):\(ke_k(x_1, \ldots x_N) = \sum_{i=1}^k (-1)^{i-1} e_{k-i}(x_1, \ldots, x_N)p_i(x_1, \ldots, x_N)\),其中\(p_i(x_1, \ldots, x_N)\) 定义为\(x_1^i + x_2^i + \cdots + x_N^i\)

证明:简单容斥,不详述

定理3:\(e_1(\lambda_1, \ldots, \lambda_N) = -c_{N-1}\)
\(e_2(\lambda_1, \ldots, \lambda_N) = +c_{N-2}\)
\(e_3(\lambda_1, \ldots, \lambda_N) = -c_{N-3}\)
\(e_4(\lambda_1, \ldots, \lambda_N) = +c_{N-4}\)
\(\ldots\)
\(e_N(\lambda_1, \ldots, \lambda_N) = (-1)^Nc_0\)

证明:根据行列式的性质,显然,不详述

我们根据定理1,暴力求出\(N\)个矩阵后,可得\(tr(H^N)\),根据定理2即\(e_k(x_1,\ldots x_N)\),再根据定理3得到系数向量\(c\)。(\(O(n^4)\))

根据特征多项式有:
\(\begin{aligned} c_0 + c_1 H + c_2 H^2 + \ldots + H^N &= 0 \\\ c_0 H^{k-N} + c_1 H^{k-N+1} + c_2 H^{k-N+2} + \ldots + H^k &= 0 \\\ ext{tr}[c_0 H^{k-N} + c_1 H^{k-N+1} + c_2 H^{k-N+2} + \ldots + H^k] &= 0 \end{aligned}\)
\(c_0 ext{tr}[H^{k-N}] + c_1 ext{tr}[H^{k-N+1}] + c_2 ext{tr}[H^{k-N+2}] + \ldots + ext{tr}[H^k] = 0\)
故我们有了\(O(nK)\)得到一张图的转移矩阵的\(K\)个迹了

设\(G_{ik}\)表示\(i\)走\(k\)步回到自己的答案,我们将\(l\)到\(r\)的\(\sum\limits G_{ik}\)相乘即可
但某一步可能一张图都没有走,也就是选出来的是个空集,这里得二项式反演一下,所以要写个\(ntt\)

具体地,把操作离线下来,复杂度\(O(T(n^4+nK)+T^2klogk)\)

code

明天写

上一篇:攻防世界upload1


下一篇:Ext.js 4.2 默认选中Grid行