remake gdkoi23 马戏团里你最忙，tensor product关于最小多项式的性质

· · 个人记录

seauy跟我说我写错了，我一看我确实写错了，这个and or不是每一位独立随机，而是所有位都and或者都or，容易看到这两者是不一样的。

所以说整个的转移矩阵其实是

q\begin{bmatrix}1&\frac{1}{2}\\0&\frac{1}{2}\end{bmatrix}^{\otimes n}+p\begin{bmatrix}\frac{1}{2}&0\\\frac{1}{2}&1\end{bmatrix}^{\otimes n}

我们简记为qA^{\otimes n}+pB^{\otimes n}。

我们之前说明了，2\times 2的矩阵的tensor product意义下的n次幂，其最小多项式次数不超过n+1。也就是说A^{\otimes n},B^{\otimes n}的最小多项式次数都不超过n+1。

这里我们可能会想用代数数的和还是代数数的证明的方法，来证明转移矩阵的最小多项式次数是O(n^2)的。但是有问题，A,B并不交换，这就寄了。

我们就需要具体去考察qA^{\otimes n},pB^{\otimes n}的最小多项式分别是什么了。可以注意到A,B根本就是相似的，有相同的最小多项式(x-1)(x-\frac{1}{2})。根据之前的讨论，A^{\otimes n},B^{\otimes n}也相似，并且它们的最小多项式都是\prod\limits_{k=0}^n(x-\frac{1}{2^k})。乘上p,q的话，把x换成\frac{x}{p},\frac{x}{q}就好了。

现在用sagemath算特征值看看，可以看到qA^{\otimes n}+pB^{\otimes n}的特征值也是这些，特征多项式也是这个（而且和p,q无关），代码如下

A=matrix(CDF,[[1,0.5],[0,0.5]])
B=matrix(CDF,[[0.5,0],[0.5,1]])
def power(A,n):
    return A if n==1 else A.tensor_product(power(A,n-1))

n=5
An=power(A,n)
Bn=power(B,n)

p,q=0.3,0.7
a=An.eigenvalues()
b=Bn.eigenvalues()
c=(p*An+q*Bn).eigenvalues()
a.sort()
b.sort()
c.sort()
print(a)
print(b)
print(c)

R.<x> = PolynomialRing(CDF, 'x')
f=1
for i in range(0,n+1):
    f=f*(x-pow(1/2,i))
print(f(p*An+q*Bn))

那么我们就要证明\prod\limits_{k=0}^n(qA^{\otimes n}+pB^{\otimes n}-\frac{1}{2^k}I)=O。这个事情我不会，先放这里让大家教教我。

好的这个事情被牛人搞定了。见https://www.luogu.me/article/x2ycdctp

答案就是要算\sum\limits_iM^{k-i}CM^kx_0，其中C是一个对角矩阵，就是那个系数。这个东西也好说，我们只需要模最小多项式把这个k项的和reduce到O(n^2)项，每一项形如c_{x,y}M^xCM^yx_0，这里暴力倍增即可，维护一个二元多项式，复杂度是关于n,\log k的多项式。

然后先对于每个y算出CM^yx_0，记为t_y，这一步复杂度是O(2^nn^2)；再对于每个x算出s_x=\sum\limits_y c_{x,y}t_y，还是O(2^nn^2)。现在剩下的问题是\sum\limits_xM^xs_x，用秦九韶算法（秦九韶优势区间，只能快速求值不能快速复合的变换），还是O(2^nn^2)。