[CF 453D] Little Pony and Elements of Harmony

作法：

這題我是看官方解寫的，但他寫的很不清楚，這裡紀錄一下詳細，雖然應該有不用用到這種東西的作法......

題目簡單來說就是要求向量$A^t\cdot e_0$是多少，其中$A$是一個$n\times n$的矩陣，滿足他的$(i,j)$項為$b[bit(i\; xor\; j)]$（其中用$bit(x)$代表$x$的二進制中$1$的個數），$e_0$則是一個給定的$n$維向量。如果$A$有$n$個線性獨立的 eigenvector，設其為$v_0,...,v_{n-1}$，並且對應的 eigenvalue 為$\lambda _0,...,\lambda _{n-1}$，那麼可以先把$e_0$拆成$v_i$的組合，也就是令$c_0,...,c_{n-1}$滿足$\displaystyle e_0=\sum_{i=0}^{n-1} c_iv_i$，那麼所求就會$\displaystyle =A^t\sum_{i=0}^{n-1} c_iv_i=\sum_{i=0}^{n-1}c_iA^tv_i =\sum_{i=0}^{n-1} c_i\lambda _i^tv_i$。所以接下來的步驟就是先求出$c_i$和$\lambda _i$，算出$v_i$前面的係數之後再想辦法組合起來。

神奇的是$A$這個矩陣的確有$n$個 eigenvector ，並且$v_i$的第$j$項恰好等於$(-1)^{bit(i\& j)}$（這篇中所有的證明都放在最後）。記矩陣$H=\begin{bmatrix}v_0 & v_1 & \dots & v_{n-1}\end{bmatrix}$，並且回到$\displaystyle e_0=\sum_{i=0}^{n-1} c_iv_i$這個式子，他就會等價於
$e_0=H\cdot \begin{bmatrix}c_0\\c_1\\\vdots\\c_{n-1}\end{bmatrix}$，所以$\begin{bmatrix}c_0\\c_1\\\vdots\\c_{n-1}\end{bmatrix}=H^{-1}e_0$。又因為$H$是對稱的，還有$v_0,...,v_{n-1}$兩兩正交，所以可以得到$H\cdot H=n\cdot I$，也就是$H^{-1}=\frac{1}{n}H$，所以這裡本質上就是要算$H$乘以一個向量得到的向量是多少。

我們把求$H$乘上一個向量的作法留到後面，先來看$\lambda _i$的求法。因為$Av_i=\lambda _iv_i$，所以我們只要比對兩邊第一項的值就好了。可以得到$\displaystyle \sum_{k=0}^{n-1} b[bit(k)](-1)^{bit(i\& k)}=\lambda _i$（這裡代入了$A$的第$(0,k)$項為$b[bit(0\; xor \; k)]=b[bit(k)]$，還有$v_i$的第$k$項為$(-1)^{bit(i\& k)}$）。令另一個$n$維向量$d$的第$k$項等於$b[bit(k)]$，那麼上式可以改寫為$\lambda _i = d \cdot v_i$，因此把$n$條式子（$i=0,...,n-1$）寫在一起就可以變成$\begin{bmatrix}\lambda _0\\\lambda _1\\\vdots\\\lambda _{n-1}\end{bmatrix}=\begin{bmatrix}v_0^T\\v_1^T\\\vdots\\v_{n-1}^T\end{bmatrix}\cdot d=H\cdot d$，因此這裡也會變成求$H$乘上一個向量的問題。

最後則是求出所求的向量$\displaystyle \sum_{i=0}^{n-1} c_i\lambda _i^tv_i$，他可以改寫成$\begin{bmatrix}v_0 & v_1 & \dots & v_{n-1}\end{bmatrix}\cdot \begin{bmatrix}c_0\lambda _0^t \\ c_1\lambda _1^t\\\vdots\\c_{n-1}\lambda _{n-1}^t \end{bmatrix}$，因此一樣是求$H$乘一個向量，所以現在問題剩下這件事要怎麼作了。事實上我們可以用遞迴來定義$H$，定義$H_0$代表只有一個$1$的$1\times 1$的矩陣，$H_i$則定義為$\begin{bmatrix}H_{i-1} & H_{i-1} \\ H_{i-1} & -H_{i-1}\end{bmatrix}$，其中他是$2^i\times 2^i$的矩陣，那麼這邊的$H$就會是$H_m$（這不難由前面$H$的定義得出）。有了這個遞迴式就能幫助我們在$O(nlogn)$的時間內算出$H$乘上一個向量是多少了。考慮「求出$H_i\begin{bmatrix}u_0 \\ \vdots \\ u_{2^i-1} \end{bmatrix}$」這個問題，由上面的遞迴式可得他就等於$\begin{bmatrix}H_{i-1} & H_{i-1} \\ H_{i-1} & -H_{i-1}\end{bmatrix}\begin{bmatrix}u_0 \\ \vdots \\ u_{2^i-1} \end{bmatrix}$，因此我們先遞迴下去算出$H_{i-1}\begin{bmatrix}u_0 \\ \vdots \\ u_{2^{i-1}-1} \end{bmatrix}$和$H_{i-1}\begin{bmatrix}u_{2^{i-1}} \\ \vdots \\ u_{2^i-1} \end{bmatrix}$，假設分別得到$U_1$和$U_2$，那麼不難得到所求就會等於$\begin{bmatrix}U_1+U_2 \\ U_1-U_2 \end{bmatrix}$，也就是能在線性的時間內合併兩個子問題，因此複雜度是$O(nlogn)$。他的寫法就有點類似FFT，但這個簡潔多了。

=======================================================================

最後補上前面沒證的證明，一個是為什麼$v_i$們就會是$A$的 eigenvector ，還有為什麼$v_i$們兩兩正交。兩兩正交比較好證，我們要證明$v_i\cdot v_j=0$（其中$i\neq j$），這等價於$\displaystyle \sum_{k=0}^{n-1} (-1)^{bit(i\& k)+bit(j\& k)}=0$，假設$i,j$的第$x$個 bit 不同，那麼考慮上式中將第$k$項和第$k\; xor \; 2^x$項配對，不難證明這兩項一個是$1$一個是$-1$，因此總和為$0$。最後證明$v_i$為 eigenvector ，考慮$Av_i=\lambda _i v_i$這式子兩邊的第$j$項，可以得到$\displaystyle \sum_{k=0}^{n-1}b[bit(j\; xor \; k)](-1)^{bit(i\& k)}=\lambda _i (-1)^{bit(i\& j)}$，我們要證明的是當$j$跑遍$0,...,n-1$時$\lambda _i$都會是固定的。考慮左式中$b[z]$的係數，可以得到他會是$\displaystyle \sum_x (-1)^{bit(i\& x)}$，其中$x$跑遍所有和$j$差了$z$個 bit 的數（也就是$bit(j\; xor \; x)=z$）。考慮把$j$的第$r$個 bit 改掉時$b[z]$的係數會如何變化，分成$i$的第$r$個 bit 是$0$或$1$兩種情況，而不管是哪種情況在計算$b[z]$的那條式子中的$x$們必須把他們的第$r$個 bit 都改掉才會滿足他和新的$j$差$z$個 bit ，因此當$i$的第$r$個 bit 是$1$的時候，對於所有的$b[z]$係數中的$(-1)^{bit(i\& x)}$都會乘上一個負號，否則係數都不會變。回到我們要證明的那條式子，剛才說明了當$j$的某個 bit 改變時左式會發生什麼事，而右式中的$(-1)^{bit(i\& j)}$也恰好會發生一樣的改變，當$j$變動的 bit 在$i$那邊也是$1$時則變為$-1$倍，否則不變，這就得到了當$j$跑遍所有$0,...,n-1$的數時$\lambda _i$都會是定值，因此$v_i$為$A$的 eigenvector。


code :

#include<bits/stdc++.h>
#define LL long long
#define bit(x) __builtin_popcount(x)
using namespace std;
const int maxm=20 , maxn=1<<maxm ;
LL MOD ;
 
inline LL llmul(LL a,LL b)
{
    LL ret=(a*b-(LL)((long double)a*b/MOD)*MOD)%MOD ;
    if(ret<0) ret+=MOD ;
    return ret ;
}
 
LL power(LL x,LL n)
{
    if(n<=1) return n ? x : 1 ;
    LL t=power(x,n/2) ;
    if(n%2) return llmul(llmul(t,t),x) ;
    else return llmul(t,t) ;
}
 
void FWT(LL *a,int n)
{
    if(n==1) return ;
    int n2=n>>1 ;
    FWT(a,n2) ; FWT(a+n2,n2) ;
    for(int i=0;i<n2;i++)
    {
        LL x=a[i] , y=a[i+n2] ;
        a[i]=(x+y)%MOD ;
        a[i+n2]=(x-y+MOD)%MOD ;
    }
}
 
LL e0[maxn],b[maxm+10],c[maxn] ;
LL ev[maxn] ; /// eigenvalue
main()
{
    int n,m ; LL t,p ; scanf("%d%lld%lld",&m,&t,&p) ;
    n=1<<m ; MOD=n*p ;
    for(int i=0;i<n;i++) scanf("%lld",&e0[i]) ;
    for(int i=0;i<=m;i++) scanf("%lld",&b[i]) ;
    for(int i=0;i<n;i++) ev[i]=b[bit(i)]%MOD ;
 
    FWT(e0,n) ;
    FWT(ev,n) ;
    for(int i=0;i<n;i++) c[i]=llmul(e0[i],power(ev[i],t)) ;
    FWT(c,n) ;
    for(int i=0;i<n;i++) printf("%lld\n",((c[i]+MOD)%MOD)>>m) ;
}