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

无关），代码如下

PYTHON

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)

。

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

文章操作

相关推荐

评论

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