T3
题意:有矩阵\(A\)与置换\(P\),给出\(A_1\).\(A_i\)=\(P(A_{i-1})\),求\(\det(A)\)
不难发现，当置换\(P\)的循环拆分个数大于\(1\)时，答案为\(0\)
不妨设拆分成了\(2\)个循环，为\(x\)与\(y\),其中\(|x|\leq |y|\)
则会发现后\(|y|\)行消去前\(|x|\)行后线性相关
大于\(2\)时归纳易证
所以我们现在就是要求一个循环矩阵\(A\)的行列式
\[A=\left[\begin{matrix}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{matrix}\right] \]设矩阵\(C=\left[\begin{matrix}1&1&\cdots&1\\1&\omega^1_n&\cdots&\omega^{n-1}_n\\1&\omega^2_n&\cdots&\omega^{2(n-1)}_n\\\vdots&\vdots&\ddots&\vdots\\1&\omega^{n-1}_n&\cdots&\omega^{(n-1)^2}_n\end{matrix}\right]\)
因为\(C\)为范德蒙矩阵
所以\(\det(C)=\sum_{0\leq i<j<n}(\omega^j-\omega^i)\not =0\)
所以\(C\)为非奇异矩阵
设\(f(x)=\sum_{i=0}^{n-1}a_ix^i\)
\[AC=\left[\begin{matrix}f(1)&f(\omega)&f(\omega^2)&\cdots&f(\omega^{n-1})\\ f(1)&\omega f(\omega)&\omega^2 f(\omega^2)&\cdots&\omega^{n-1} f(\omega^{n-1})\\\vdots&\vdots&\vdots&\ddots&\vdots\\f(1)&\omega^{(n-1)} f(\omega)&\omega^{2(n-1)} f(\omega^2)&\cdots&\omega^{(n-1)^2} f(\omega^{n-1})\end{matrix}\right]=\left(\prod_{i=0}^{n-1}f(\omega^i)\right)C\\ \Leftrightarrow \det(A)\det(C)=\left(\prod_{i=0}^{n-1}f(\omega^i)\right)\det(C)\\ \Leftrightarrow \det(A)=\prod_{i=0}^{n-1}f(\omega^i) \]所以怎么求\(\prod_{i=0}^{n-1}f(\omega^i)\)呢？
如果不带模，我们可以直接用离散傅里叶变换
可是带模
我们可以发现，\(\omega^i\)其实就是多项式\(g(x)=x^n-1\)的根
设\(\lambda_{0\sim n-1}\)表示\(n\)次多项式\(A\)的\(n\)个根
设\(\zeta_{0\sim m-1}\)表示\(m\)次多项式\(B\)的\(m\)个根
则\(A=([x^n]A)\prod_{i=0}^{n-1}(x-\lambda_i)\)
定义函数\(\gamma(A,B)\)表示\(([x^m]B)^n\prod_{i=0}^{m-1}A(\zeta_i)\)
\[\begin{align} \gamma(A,B)&=([x^m]B)^n\prod_{i=0}^{m-1}A(\zeta_i)\\ &=([x^m]B)^n\prod_{i=0}^{m-1}([x^n]A)\prod_{j=0}^{n-1}(\zeta_i-\lambda_j)\\ &=([x^m]B)^n([x^n]A)^m\prod_{i=0}^{m-1}\prod_{j=0}^{n-1}(\zeta_i-\lambda_j)\\ &=(-1)^{nm}([x^n]A)^m\prod_{i=0}^{n-1}B(\lambda_i)\\ &=(-1)^{nm}\gamma(B,A) \end{align} \] \[\begin{align} \gamma(A-B,B)&=([x^m]B)^n\prod_{i=0}^{m-1}(A(\zeta_i)-B(\zeta_i))\\ &=([x^m]B)^n\prod_{i=0}^{m-1}A(\zeta_i)\\ &=\gamma(A,B) \end{align} \] \[\gamma(A,B)=A^m(A为常函数) \] \[\begin{align} \gamma(kA,B)&=([x^m]B)^n\prod_{i=0}^{m-1}kA(\zeta_i)\\ &=([x^m]B)^nk^m\prod_{i=0}^{m-1}A(\zeta_i)\\ &=k^m\gamma(A,B) \end{align} \]同理\(\gamma(A,kB)=(-1)^{nm}\gamma(kB,A)=k^n\gamma(A,B)\)
这样我们就可以像\(\tt gcd\)一样在\(O(n^2)\)的时间内求出来了
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;char k;bool vis=0;
do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 1000000007
int s,q[5005],a[5005],b[5005];
ll qkpow(ll n,int m){
ll t=1;
for(;m;m>>=1,n=n*n%mod)
if(m&1)t=t*n%mod;
return t;
}
int main(){fre("matrix");
s=read;
for(int i=1;i<=s;++i)a[i]=read;
for(int i=1;i<=s;++i)q[read]=i;
for(int i=1,t=1;t<=s;++t,i=q[i]){
if(i==1&&t!=1)return puts("0"),0;
b[t]=i;
}ll ans=1;
for(int i=1;i<=s;b[i-1]=a[b[i]],++i)
for(int j=i+1;j<=s;++j)
if(b[i]>b[j])
ans=-ans;
memset(a,0,sizeof(a));
int n=s,m=s-1;
a[n]=1;a[0]=-1;
while(1){
if(n<m)swap(n,m),(n&m&1)&&(ans=-ans),swap(a,b);
if(!m){
ans=ans*qkpow(b[0],n)%mod;
break;
}
for(int i=n-m;~i;--i){
if(!a[i+m])continue;
ll x=qkpow(b[m],mod-2)*a[i+m]%mod;
for(int j=0;j<=m;++j)
a[i+j]=(a[i+j]-b[j]*x)%mod;
}
int tv=n;
while(!a[n]&&n)--n;
ans=ans*qkpow(b[m],tv-n)%mod;
}printf("%lld",(ans+mod)%mod);
return 0;
}
### T3
> 题意:有矩阵$A$与置换$P$,给出$A_1$.$A_i$=$P(A_{i-1})$,求$\det(A)$
不难发现，当置换$P$的循环拆分个数大于$1$时，答案为$0$
不妨设拆分成了$2$个循环，为$x$与$y$,其中$|x|\leq |y|$
则会发现后$|y|$行消去前$|x|$行后线性相关
大于$2$时归纳易证
所以我们现在就是要求一个循环矩阵$A$的行列式
$$
A=\left[\begin{matrix}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{matrix}\right]
$$
设矩阵$C=\left[\begin{matrix}1&1&\cdots&1\\1&\omega^1_n&\cdots&\omega^{n-1}_n\\1&\omega^2_n&\cdots&\omega^{2(n-1)}_n\\\vdots&\vdots&\ddots&\vdots\\1&\omega^{n-1}_n&\cdots&\omega^{(n-1)^2}_n\end{matrix}\right]$
因为$C$为范德蒙矩阵
所以$\det(C)=\sum_{0\leq i<j<n}(\omega^j-\omega^i)\not =0$
所以$C$为非奇异矩阵
设$f(x)=\sum_{i=0}^{n-1}a_ix^i$
$$
AC=\left[\begin{matrix}f(1)&f(\omega)&f(\omega^2)&\cdots&f(\omega^{n-1})\\
f(1)&\omega f(\omega)&\omega^2 f(\omega^2)&\cdots&\omega^{n-1} f(\omega^{n-1})\\\vdots&\vdots&\vdots&\ddots&\vdots\\f(1)&\omega^{(n-1)} f(\omega)&\omega^{2(n-1)} f(\omega^2)&\cdots&\omega^{(n-1)^2} f(\omega^{n-1})\end{matrix}\right]=\left(\prod_{i=0}^{n-1}f(\omega^i)\right)C\\
\Rightarrow \det(A)\det(C)=\left(\prod_{i=0}^{n-1}f(\omega^i)\right)\det(C)\\
\Rightarrow \det(A)=\prod_{i=0}^{n-1}f(\omega^i)
$$
所以怎么求$\prod_{i=0}^{n-1}f(\omega^i)$呢？
如果不带模，我们可以直接用离散傅里叶变换
可是带模
我们可以发现，$\omega^i$其实就是多项式$g(x)=x^n-1$的根
设$\lambda_{0\sim n-1}$表示$n$次多项式$A$的$n$个根
设$\zeta_{0\sim m-1}$表示$m$次多项式$B$的$m$个根
则$A=([x^n]A)\prod_{i=0}^{n-1}(x-\lambda_i)$
定义函数$\gamma(A,B)$表示$([x^m]B)^n\prod_{i=0}^{m-1}A(\zeta_i)$
$$
\begin{align}
\gamma(A,B)&=([x^m]B)^n\prod_{i=0}^{m-1}A(\zeta_i)\\
&=([x^m]B)^n\prod_{i=0}^{m-1}([x^n]A)\prod_{j=0}^{n-1}(\zeta_i-\lambda_j)\\
&=([x^m]B)^n([x^n]A)^m\prod_{i=0}^{m-1}\prod_{j=0}^{n-1}(\zeta_i-\lambda_j)\\
&=(-1)^{nm}([x^n]A)^m\prod_{i=0}^{n-1}B(\lambda_i)\\
&=(-1)^{nm}\gamma(B,A)
\end{align}
$$
$$
\begin{align}
\gamma(A-B,B)&=([x^m]B)^n\prod_{i=0}^{m-1}(A(\zeta_i)-B(\zeta_i))\\
&=([x^m]B)^n\prod_{i=0}^{m-1}A(\zeta_i)\\
&=\gamma(A,B)
\end{align}
$$
$$
\gamma(A,B)=A^m(A为常函数)
$$
$$
\begin{align}
\gamma(kA,B)&=([x^m]B)^n\prod_{i=0}^{m-1}kA(\zeta_i)\\
&=([x^m]B)^nk^m\prod_{i=0}^{m-1}A(\zeta_i)\\
&=k^m\gamma(A,B)
\end{align}
$$
同理$\gamma(A,kB)=(-1)^{nm}\gamma(kB,A)=k^n\gamma(A,B)$
这样我们就可以像$\tt gcd$一样在$O(n^2)$的时间内求出来了
```cpp
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;char k;bool vis=0;
do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 1000000007
int s,q[5005],a[5005],b[5005];
ll qkpow(ll n,int m){
ll t=1;
for(;m;m>>=1,n=n*n%mod)
if(m&1)t=t*n%mod;
return t;
}
int main(){fre("matrix");
s=read;
for(int i=1;i<=s;++i)a[i]=read;
for(int i=1;i<=s;++i)q[read]=i;
for(int i=1,t=1;t<=s;++t,i=q[i]){
if(i==1&&t!=1)return puts("0"),0;
b[t]=i;
}ll ans=1;
for(int i=1;i<=s;b[i-1]=a[b[i]],++i)
for(int j=i+1;j<=s;++j)
if(b[i]>b[j])
ans=-ans;
memset(a,0,sizeof(a));
int n=s,m=s-1;
a[n]=1;a[0]=-1;
while(1){
if(n<m)swap(n,m),(n&m&1)&&(ans=-ans),swap(a,b);
if(!m){
ans=ans*qkpow(b[0],n)%mod;
break;
}
for(int i=n-m;~i;--i){
if(!a[i+m])continue;
ll x=qkpow(b[m],mod-2)*a[i+m]%mod;
for(int j=0;j<=m;++j)
a[i+j]=(a[i+j]-b[j]*x)%mod;
}
int tv=n;
while(!a[n]&&n)--n;
ans=ans*qkpow(b[m],tv-n)%mod;
}printf("%lld",(ans+mod)%mod);
return 0;
}