2024.11.8 鮮花
Moon Halo
Some deserts on this planet were oceans once
這顆星球上的一些沙漠曾是海洋
Somewhere shrouded by the night, the sun will shine
被黑夜籠罩的地方，也會(huì)迎來(lái)光明
Sometimes I see a dying bird fall to the ground
偶爾也會(huì)見(jiàn)到瀕死的鳥(niǎo)跌落地面
But it used to fly so high
但它也曾展翅高飛
I thought I were no more than a bystander till I felt a touch so real
我本以為我不過(guò)是個(gè)旁觀者 直到我感覺(jué)到如此真實(shí)的觸覺(jué)
I will no longer be a transient when I see smiles with tears
當(dāng)我看到人們含淚的微笑 我便不再是個(gè)匆匆過(guò)客
If I have never known the sore of farewell and pain of sacrifices
如果不曾知曉生離死別的傷痛
What else should I engrave on my mind
我又該將什么銘記于心
Frozen into icy rocks, that's how it starts
冰凍成石一般的開(kāi)端
Crumbled like the sands of time, that's how it ends
沙漏崩落一般的終結(jié)
Every page of tragedy is thrown away burned out in the flame
悲劇的每一頁(yè)已被焚燒殆盡
A shoulder for the past
給過(guò)往一個(gè)肩膀
Let out the cries imprisoned for so long
讓久被禁錮的哭泣得以放聲
A pair of wings for me at this moment
給此刻的自己一雙翅膀
To soar above this world
翱翔于世界之上
Turn into a shooting star that briefly shines but warms up every heart
化為一顆流星，給每個(gè)心靈一瞬的希望
May all the beauty be blessed
愿所有的美好都能得到祝福
May all the beauty be blessed
愿所有的美好都能得到祝福
I will never go
我不會(huì)離開(kāi)
There's a way back home
這就是我們的歸途
Brighter than tomorrow and yesterday
比過(guò)往與未來(lái)都要更加閃耀著
May all the beauty be blessed
愿所有的美好都能得到祝福
Wave good-bye to the past when hope and faith have grown so strong and sound
當(dāng)希望和信念羽翼豐滿(mǎn)，就向昨日告別吧
Unfold this pair of wings for me again
再一次為我張開(kāi)這雙羽翼
To soar above this world
翱翔于世界之上
Turned into a moon that always tells the warmth and brightness of the sun
化為月亮長(zhǎng)久地傳達(dá)著太陽(yáng)的光耀
May all the beauty be blessed
愿所有的美好都能得到祝福
May all the beauty be blessed
愿所有的美好都能得到祝福
你說(shuō)得對(duì)，沒(méi)人問(wèn)我，但這是我們初一第一首起床鈴
sosdp,FMT,FWT 下
不是，怎么 FMT 只有板子和不可做題啊！！！
那就先放板子吧：CF582E Boolean Function
solution
起手建表達(dá)式樹(shù)。
\(A,B,C,D\) 只有四個(gè)，直接狀壓，設(shè) \(dp_{i,j}\) 表示在 \(i\) 的子樹(shù)內(nèi)，狀態(tài)為 \(j\) 的方案數(shù)，轉(zhuǎn)移就是 OR 和 AND 卷積。
但是隊(duì)奶告訴我可以 FMT 可以直接求異或卷積，快快推薦一下。
感覺(jué)放課件太魔怔了，想看的可以看 this，就復(fù)述一下把。
考慮前綴和時(shí)第 \(i\) 維實(shí)際上是由兩個(gè)第 \(i-1\) 維組成的，設(shè)其前綴和完 \(i-1\) 維的值為 \(a_i,b_i\)，那么前綴和實(shí)際上就是變成了 \(a_i,b_i+a_i\)。
類(lèi)似定義新運(yùn)算，依次對(duì)第 \(i\) 維做 \(a_i+b_i,a_i-b_i\)。
逆運(yùn)算是顯然的 \(\frac{a_i+b_i}2,\frac{a_i-b_i}2\)
于是我們用這個(gè)做莫變即可。
證明：\((a_i,b_i)*(c_i,d_i)\to(a_i+b_i,a_i-b_i)(c_i+d_i,c_i-d_i)=(a_ic_i+a_id_i+b_ic_i+b_id_i,a_ic_i-a_id_i-b_ic_i+b_id_i)\to(a_ic_i+b_id_i,a_id_i+b_ic_i)\)
于是就有真正的板子了：P4717 【模板】快速莫比烏斯/沃爾什變換 (FMT/FWT)
放個(gè)代碼：
Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=stdin,*OutFile=stdout;
#endif
const int N=1<<17|3,MOD=998244353,Inv=(MOD+1)/2;
int Add(int a,int b){return (a+=b)>=MOD?a-MOD:a;}
int Sub(int a,int b){return (a-=b)<0?a+MOD:a;}
int ca[N],cb[N],a[N],b[N],n;
void Fmt(int *f,const function<void(int &,int &)> &F){for(int i=1;i<n;i<<=1) for(int j=0;j<n;++j) if(j&i) F(f[j^i],f[j]);}
const function<void(int &,int &)>
Or=[](int &a,int &b){b=Add(a,b);},
And=[](int &a,int &b){a=Add(a,b);},
Xor=[](int &a,int &b){int t=a; a=Add(a,b),b=Sub(t,b);};
void Cp(){memcpy(a,ca,sizeof a),memcpy(b,cb,sizeof b);}
void Mrg(){for(int i=1;i<=n;++i) a[i]=1ll*a[i]*b[i]%MOD;}
void Out(){for(int i=1;i<=n;++i) cout<<a[i]<<' '; cout<<endl;}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n; n=1<<n; for(int i=1;i<=n;++i) cin>>ca[i]; for(int i=1;i<=n;++i) cin>>cb[i];
Cp(),Fmt(a+1,Or),Fmt(b+1,Or),Mrg(),Fmt(a+1,[](int &a,int &b){b=Sub(b,a);}),Out();
Cp(),Fmt(a+1,And),Fmt(b+1,And),Mrg(),Fmt(a+1,[](int &a,int &b){a=Sub(a,b);}),Out();
Cp(),Fmt(a+1,Xor),Fmt(b+1,Xor),Mrg(),Fmt(a+1,[](int &a,int &b){int t=a; a=1ll*(a+b)*Inv%MOD,b=1ll*(t-b+MOD)*Inv%MOD;}),Out();
}
但只會(huì)這個(gè)還不夠，你還要會(huì)寫(xiě)子集卷積。
求 \(h(S)=\sum_{T\subseteq S} f(T)g(S-T)\)
你發(fā)現(xiàn)這個(gè)相較于 OR 卷積多出了一個(gè) \(A\cap B = \varnothing\)。
發(fā)現(xiàn) \(A\cap B = \varnothing\Leftrightarrow |A|+|B|=|A \cup B|\)
所以如果我們每次只考慮大小為 \(p\) 的集合，將所的函數(shù)記為 \(f_p\)，有 \(h_{i+j}(S)=\sum_{T\subseteq S} f_i(T)g_j(S-T)\)
所以對(duì)每一個(gè) \(p\) 單獨(dú)計(jì)算最后在暴力卷積即可，復(fù)雜度 \(n^22^n\) 或 \(n\log^2 n\)。
Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=stdin,*OutFile=stdout;
#endif
const int N=1<<20|3,MOD=1e9+9,Inv=(MOD+1)/2;
int Add(int a,int b){return (a+=b)>=MOD?a-MOD:a;}
int Sub(int a,int b){return (a-=b)<0?a+MOD:a;}
int n,ca[23][N],cb[23][N],aas[23][N];
void Fmt(int *f,const function<void(int &,int &)> &T){for(int i=0;i<n;++i) for(int j=0;j<1<<n;++j) if(j>>i&1) T(f[j^1<<i],f[j]);}
const function<void(int &,int &)> Or=[](int &a,int &b){b=Add(a,b);},IOr=[](int &a,int &b){b=Sub(b,a);};
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n; for(int i=0;i<1<<n;++i) cin>>ca[__builtin_popcount(i)][i]; for(int i=0;i<1<<n;++i) cin>>cb[__builtin_popcount(i)][i];
for(int i=0;i<=n;++i) Fmt(ca[i],Or),Fmt(cb[i],Or);
for(int i=0;i<=n;++i) for(int j=0;j<=i;++j) for(int s=0;s<1<<n;++s) aas[i][s]=Add(aas[i][s],1ll*ca[j][s]*cb[i-j][s]%MOD);
for(int i=0;i<=n;++i) Fmt(aas[i],IOr); for(int i=0;i<1<<n;++i) cout<<aas[__builtin_popcount(i)][i]<<' ';
}
FWT
其實(shí) FWT 和 FMT 本質(zhì)是一個(gè)東西，它們倆變換出來(lái)的多項(xiàng)式都一模一樣。
上次也說(shuō)了，F(xiàn)WT 是基于變換的思想實(shí)現(xiàn)的，和 FFT 更相似，也更難寫(xiě)，所以學(xué)這個(gè)不是為了寫(xiě)板子的，其實(shí)是在學(xué)一些性質(zhì)和構(gòu)造本質(zhì)的東西。
可以先去模板題的題解看一下板子。
容易發(fā)現(xiàn)，這個(gè)東西是線性變換，所以有 \(FWT(A+B)=FWT(A)+FWT(B),FWT(cA)=cFWT(A)\)。
以下的 \(i,j\) 都表示狀壓后的狀態(tài)。
我們?cè)O(shè)，對(duì)于第 \(i\) 個(gè)元素，他會(huì)給每個(gè) \(j\in[1,n]\) 貢獻(xiàn) \(c(i,j)\) 次，其實(shí)用矩陣乘法表示就是那個(gè)矩陣。
容易發(fā)現(xiàn)，對(duì)于 OR 卷積，\(c(i,j)=[i\&j==i]\)，AND 卷積，\(c(i,j)=[i\&j==i]\)，XOR 卷積，\(c(i,j)=(-1)^{popcount(i\&j)}\)
知道了上面的，來(lái)做好題：CF1119H Triple
solution
首先暴力卷積是顯然的，考慮以 \(a,b,c\) 為指數(shù)，\(x,y,z\) 為對(duì)應(yīng)系數(shù)，直接做異或卷積即可，復(fù)雜度 \(nk2^k\)，過(guò)不去。
發(fā)現(xiàn)只有三個(gè)位置有值，對(duì)于每個(gè)的莫變可以暴力乘上貢獻(xiàn)次數(shù)，這樣的復(fù)雜度是 \((n+k)2^k\)，還是過(guò)不去。
發(fā)現(xiàn)最后的卷積數(shù)組 \(S\) 的第 \(i\) 項(xiàng) \(S_i=\prod\limits_{k=1}^n c(k,a_k)x+c(k,b_k)y+c(k,c_k)z\)
后面的取值只有 \(8\) 種可能，如果你有耐心，依據(jù)接下來(lái)的規(guī)律找出 \(8\) 種次數(shù)的 \(8\) 個(gè)方程也是不難做到的，但是可以減少情況。
考慮將 \(a,b,c\) 都 \(\oplus a\)，最后查詢(xún)時(shí)也 \(\oplus a\)，這樣 \(c(k,a_k)=c(k,0)=1\)，所以只有 \(4\) 種情況。
考慮設(shè) \(x+y+z,x+y-z,x-y+z,x-y-z\) 的次數(shù)分別為 \(t_1,t_2,t_3,t_4\)，考慮解方程，顯然的第一個(gè)方程是 \(t_1+t_2+t_3+t_4=n\)
發(fā)現(xiàn) \(y\) 和 \(z\) 的符號(hào)互相無(wú)關(guān)，考慮 \(y\) 的系數(shù)，將 \(x=0,y=1,z=0\) 帶入變換，得到的結(jié)果為 \(FMT(G_i)\)，則有 \(\sum FMT(G_i)=\sum c(k,b_k)=t_1+t_2-t_3-t_4\)，計(jì)算 \(\sum FMT(G_i)\) 是容易的，發(fā)現(xiàn) FMT 是線性變換，求 \(FMT(G'[k]=\sum[b_k=k])\) 即可。
對(duì)于 \(z\) 做類(lèi)似處理可以在得到一個(gè)方程，考慮最后一個(gè)方程，發(fā)現(xiàn)其應(yīng)該由 \(y,z\) 共同給出，于是對(duì)于每個(gè) \(i\) 將 \(F_i[b_i\oplus c_i]=1\)（這里 \(F[k]\) 表示多項(xiàng)式 \(F\) 的 \(k\) 次系數(shù)，前面的兩種帶入可以視為 \(G_i=F_i[b_i]=1\) 和 \(G_i=F_i[c_i]=1\) ），容易發(fā)現(xiàn)其卷積結(jié)果是 \(\sum c(i,b_i)c(i,c_i)=t_1-t_2-t_3+t_4\)。
解方程即可，最后做一遍 IFMT 即可，復(fù)雜度 \(O((k+\log n)2^k)\)。
Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=stdin,*OutFile=stdout;
#endif
const int N=2e5+3,MOD=998244353,Inv=(MOD+1)/2;
int n,m,x,y,z,p1[N],p2[N],p3[N],aas[N],sa;
int Fpw(int a,int b){
int ans=1;
while(b){
if(b&1) ans=1ll*a*ans%MOD;
a=1ll*a*a%MOD,b>>=1;
}
return ans;
}
void Fmt(int *f,const function<void(int &,int &)> &F){for(int i=1;i<m;i<<=1) for(int j=0;j<m;++j) if(j&i) F(f[j^i],f[j]);}
const auto Xor=[](int &a,int &b){int t=a; a=(a+b)%MOD,b=(t-b)%MOD;};
const auto IXr=[](int &a,int &b){int t=a; a=1ll*(a+b)*Inv%MOD,b=1ll*(t-b)*Inv%MOD;};
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>x>>y>>z,m=1<<m; for(int i=1;i<=n;++i){int a,b,c; cin>>a>>b>>c; sa^=a,b^=a,c^=a,++p1[b],++p2[c],++p3[b^c];}
Fmt(p1,Xor),Fmt(p2,Xor),Fmt(p3,Xor); int s1=(1ll*x+y+z)%MOD,s2=(1ll*x+y-z)%MOD,s3=(1ll*x-y+z)%MOD,s4=(1ll*x-y-z)%MOD;
for(int i=0;i<m;++i){
int c1=(1ll*n+p1[i]+p2[i]+p3[i])/4,
c2=(1ll*n+p1[i]-c1-c1)/2,
c3=(1ll*n+p2[i]-c1-c1)/2,
c4=(1ll*n+p3[i]-c1-c1)/2;
aas[i]=1ll*Fpw(s1,c1)*Fpw(s2,c2)%MOD*Fpw(s3,c3)%MOD*Fpw(s4,c4)%MOD;
}
Fmt(aas,IXr); for(int i=0;i<m;++i) cout<<(aas[i^sa]+MOD)%MOD<<' ';
}
擴(kuò)展到 \(k\) 進(jìn)制
對(duì)于取 \(max,min\) 可以直接套 \(FMT\)，因?yàn)槠浔举|(zhì)是前后綴和，但是不進(jìn)位加法涉及一些深刻矛盾，我還不會(huì)，等我會(huì)了在寫(xiě)。
P
本文來(lái)自博客園，作者：xrlong，轉(zhuǎn)載請(qǐng)注明原文鏈接：http://www.rzrgm.cn/xrlong/p/18534992
版權(quán)聲明：本作品采用 「署名-非商業(yè)性使用-相同方式共享 4.0 國(guó)際」許可協(xié)議（CC BY-NC-SA 4.0） 進(jìn)行許可。
浙公網(wǎng)安備 33010602011771號(hào)