「2020-06-28 NOI 模拟赛」置换矩阵

题目链接

题意

给定长度为 $n$ 的序列 $a,p$，矩阵 $A$ 由下列规则生成，求 $\det(A)\bmod(10^9+7)$。

• $A_{1,j}=a_j$；
• $\forall i>1,A_{i,j}=A_{i-1,p_j}$。

思路

观察到有一档部分分是置换 $p$ 的环个数 $>1$，发现此时行列式值必为 $0$，证明可以分环数 $=2$ 或 $>2$ 讨论（$>2$ 的时候可以消去最小的环转为子问题）。

对于只有一个环的情况，可以改为求循环矩阵行列式。

$\begin{aligned} A&=\begin{bmatrix}a_0&a_1&\cdots&a_{n-1}\\a_{n-1}&a_0&\cdots&a_{n-2}\\\vdots&\vdots&\ddots&\vdots\\a_1&a_2&\cdots&a_0\end{bmatrix}\\ \xi&=\begin{bmatrix}\omega_n^0\\\omega_n^1\\\vdots\\\omega_n^{n-1}\end{bmatrix}\\ A\xi&=\begin{bmatrix}\sum_{i=0}^{n-1}a_i\omega_n^i\\\sum_{i=0}^{n-1}a_i\omega_n^{i+1}\\\vdots\\\sum_{i=0}^{n-1}a_i\omega_n^{i+n-1}\end{bmatrix}\\ &=\left(\sum_{i=0}^{n-1}a_i\omega_n^i\right)\xi \end{aligned}$

即对于每个 $n$ 阶复根 $\omega_n$，都有一个特征向量 $\xi$，它们线性无关，所以你就得到了 $n$ 个特征值 $\sum_{i=0}^{n-1}a_i\omega_n^i$，它们的乘积就是 $\det(A)$。

但是，在 $\bmod(10^9+7)$ 意义下，有些 $n$ 阶复根无法被整数表示，我们需要引入一种科技：把多项式 $A$ 的所有零点代入多项式 $B$ 并对函数值求积。

把多项式写成零点式，记 $A=k_A\prod_{i=0}^{n-1}(x-s_i)$，$B=k_B\prod_{i=0}^{m-1}(x-t_i)$，则：

$\begin{aligned} \prod_{i=0}^{n-1}B(s_i)&=\prod_{i=0}^{n-1}k_A\prod_{j=0}^{m-1}(s_i-t_j)\\ &=k_A^n\prod_{i=0}^{n-1}\prod_{j=0}^{m-1}(s_i-t_j)\\ &=(-1)^{nm}\frac{k_A^n}{k_B^m}\prod_{j=0}^{m-1}k_B\prod_{i=0}^{n-1}(t_j-s_i)\\ &=(-1)^{nm}\frac{k_A^n}{k_B^m}\prod_{i=0}^{m-1}A(t_i) \end{aligned}$

这样就交换了 $A$ 和 $B$ 的地位。
而 $B$ 显然可以对 $A$ 取模，我们就可以做一个类似辗转相除的过程，把答案解出来。

在本题中，$A=x^n-1$，$B=\sum_{i=0}^{n-1}a_ix^i$。

实现

直接使用暴力多项式取模即可，时间复杂度 $\mathcal O(n^2)$。

代码

#include<fstream>
#include<algorithm>
using namespace std;
const int N=5000,mod=1e9+7;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
int n;
int a[N+1],p[N+1];
int c,v[N+1];
int res;
int pow(int x,int t)
{
    int r=1;
    do {
        (t%2)&&(r=1ll*r*x%mod);
    } while(x=1ll*x*x%mod,t/=2);
    return r;
}
inline int inv(int x)
{
    return pow(x,mod-2);
}
inline int ipow(int x,int t)
{
    return pow(x,1ll*t*(mod-2)%(mod-1));
}
struct poly {
    int n,a[N+1];
    inline int &operator[](int x)
    {
        return a[x];
    }
    inline int operator[](int x) const
    {
        return a[x];
    }
    friend poly &operator%=(poly &x,const poly &y)
    {
        while(x.n>=y.n) {
            int w=1ll*x[x.n]*inv(y[y.n])%mod;
            for(int i=0;i<=y.n;++i) {
                x[x.n-i]=(x[x.n-i]-1ll*y[y.n-i]*w)%mod;
            }
            while(x.n&&!x[x.n]) {
                --x.n;
            }
        }
        return x;
    }
    friend inline void swap(poly &x,poly &y)
    {
        swap(x.n,y.n),swap(x.a,y.a);
        return;
    }
} f,g;
int main()
{
    fin>>n;
    for(int i=1;i<=n;++i) {
        fin>>a[i];
    }
    for(int i=1;i<=n;++i) {
        fin>>p[i];
    }
    for(int i=1;v[++c]=(i=p[i]),i!=1;);
    if(c!=n) {
        res=0;
        goto output;
    }
    reverse(v+1,v+n+1);
    res=1;
    for(int i=1;i<n;++i) {
        for(int j=i+1;j<=n;++j) {
            if(v[i]>v[j]) {
                res=-res;
            }
        }
    }
    f.n=n-1;
    for(int i=1;i<=n;++i) {
        f[i-1]=a[v[i]];
    }
    g.n=n,g[0]=-1,g[n]=1;
    while(f.n) {
        res=1ll*res*(f.n*g.n%2?-1:1)*pow(f[f.n],g.n)%mod*ipow(g[g.n],f.n)%mod;
        g%=f,swap(f,g);
    }
    res=1ll*res*pow(f[0],g.n)%mod;
    output: fout<<(res+mod)%mod<<endl;
    return 0;
}