题解：P10106 [GDKOI2023 提高组] 马戏团里你最忙

masterhuang · 2025-10-30 10:36:57 · 题解

马戏团里我最忙！

哈哈受某错误想法蛊惑，题解原先假了一次，原先第一步就错了，现在修订正确。

首篇做法优秀（不是瞎 BM 算）的有证明题解。

• 参考文章：remake tensor product 关于最小多项式的性质，某篇不那么牛的题解。

• 本文需要一定线性代数基础，若遇到不懂知识点或名词可以查阅资料。

• 目前这篇是 最优最短解，推荐学习。

这里我们引入张量积的概念，仅仅辅助理解。

已知 A 是一个 2\times 2 的 01 矩阵。

定义张量积幂次 A^{\otimes n}_{i,j}=\prod\limits_{k=0}^n A_{i(k),j(k)}，其中 x(k) 表示 x 的二进制第 k 位。

例如 \text{OR} 的 \text{FWT} 矩阵就是 \begin{bmatrix} 1 & 0 \\ 1 & 1\end{bmatrix}^{\otimes n}

首先先写出暴力：设 f_{i,j}, g_{i,j} 分别为第 i 次操作之后为 j 的概率、与到 j 的答案，转移 FWT 一下。

具体的，考虑 (f_i,g_i)\to (f_{i+1},g_{i+1}) 是一个线性变换，我们尝试写出转移矩阵：

令 q=1-p，定义矩阵：

相当于它达到了如下 f\gets \text{trans}(f) 的效果。

inline void trans(int *f)
{
    static int a[M],b[M];
    for(int i=0;i<m;i++) a[i]=1ll*f[i]*p%mod,b[i]=1ll*f[i]*q%mod;
    OR(a,1);AND(b,1);
    for(int i=0;i<m;i++) a[i]=(((LL)a[i])<<pc(i))%mod,b[i]=(((LL)b[i])<<(n-pc(i)))%mod;
    OR(a,0),AND(b,0);
    for(int i=0;i<m;i++) ad(f[i]=a[i],b[i]);
}// trans f=Af

下面 \cdot 是点乘，粗体表示向量，则转移就是：

于是我们只需快速求出 \mathcal{T}^K。相当于我们要求出 \mathcal{T} 的 最小多项式 m_{\mathcal{T}}(x)，然后做个齐次递推。

• 注意这里不是特征多项式！请思考 最小多项式 和 特征多项式 的区别。

先求 m_A(x)。

由于 相似变换 不改变最小多项式，于是尝试构造 相似变换。

构造 Z=\begin{bmatrix} 1 & 1 \\ 1 & -1\end{bmatrix}，发现 Z 把 X,Y 同时相似对角化了！

设 U=X^{\otimes n},V=Y^{\otimes n},W=Z^{\otimes n}，此时 W^{-1}AW=pY'^{\otimes n}+qX'^{\otimes n}=A'。

此时 A' 是一个下三角矩阵，所以它的全部不重特征值就是它的对角线元素构成的集合：\{1,2^{-1},\cdots,2^{-n}\}。

由此合理猜测 m_A(x)=\prod\limits_{i=0}^n (x-2^{-i})。

但是这样还不够，我们还要证明最小多项式里所有的根都是一阶的，这等价于这个矩阵是 可对角化的。

:::info[证明]

考虑算出 A' 矩阵，显然当 j\sube i 时 A'_{i,j} 才有值，定义 |x|=\text{popcount}(x)：

我们发现 A'_{i,j} 只和 |i|,|j| 相关。

于是我们不妨对 A' 的下标施加一个排列 p，即换基变换，此时不影响 A 是否对角化。

把 A' 如下分块，即把 \text{popcount} 相同的集中到一个区间内。