2024.11.10 鮮花
Triple 擴展
像神一樣吶
愛のネタバレ
「別れ」っぽいな
人生のネタバレ
「死ぬ」っぽいな
なにそれ意味深で
かっこいいじゃん
それっぽい単語集で踴ってんだ
失敬
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
ぽいじゃん ぽいじゃん
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
神っぽいな
もういいぜ もういいぜ それ
もういいぜ もういいぜ
逆に興奮してきたなあ
おっきいね おっきいね 夢
おっきいね おっきいね
景気いいけど 品性はthe end
うええい うええい
"Gott ist tot"
神っぽいな それ 卑怯
神っぽいな それ "my god"
アイウォンチュー ウォンチュー
IQが下がっていく感じ
邪心ぽいな それ 畢竟
邪心ぽいな それ "my god"
アイヘイチュー ヘイチュー
害蟲はどっち
その髪型 その目 その口元
その香水 その服 そのメイク
アレっぽいな それ 比況
アレっぽいな それ
その名言 その意見 その批評
そのカリスマ
そのギャグ そのセンス
神っぽいな それ 卑怯
ぽいな ぽいな ぽい 憧れちゃう
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
ぽいじゃん ぽいじゃん
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
神っぽいな
メタ思考する本質(zhì)は悪意？
人を小馬鹿にしたような作為
無為に生き延びるのは難しい
権力に飲まれて揺らぐ燈り
神を否定し神に成り代わり
玉座で豹変する小物達
批判に見せかけ自戒の祈り
Do you know？
何言ってんの？ それ ウザい
何言ってんの？ それ
意味がよくわかんないし
眠っちゃうよ マジ
飽きっぽいんだ オーケー
みんな 飽きっぽいんだ オーケー
踴れるやつ
ちょうだい ちょうだい ビーム
きっしょいね きっしょいね それ
きっしょいね きっしょいね
逆にファンになってきたじゃん
ちっちゃいね ちっちゃいね 器
ちっちゃいね ちっちゃいね
天才ゆえ孤獨ですね
かっけえ かっけえ
"Gott ist tot"
神っぽいな それ 卑怯
神っぽいな それ "my god"
超健康 健康 言い張って
くたばっていく感じ
ヤケっぽいな それ 畢竟
ヤケっぽいな それ "my god"
もう哀愁 哀愁
エピゴーネンのヒール
そのタイトル その絵
そのストーリー
その音楽 その歌 そのメロディ
アレっぽいな それ 比況
アレっぽいな それ
その名言 その意見 その批評
そのカリスマ
そのギャグ そのセンス
神っぽいな それ 卑怯
ぽいな ぽいな ぽい 憧れちゃうわ
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
ぽいじゃん ぽいじゃん
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
神っぽいな
愛のネタバレ
「別れ」っぽいな
人生のネタバレ
「死ぬ」っぽいな
すべて理解して患った
無邪気に踴っていたかった 人生
miaomaio：什么玩意，聽得腦袋疼，下回請你們聽兒歌。
Upd on 2025.8.28 建議看這個
上次鮮花已經(jīng)講了這題做法，就不在贅述了。
考慮擴展，形式化的，求：
給定 \(n,m,k\)，有 \(n\) 個多項式 \(f_i=\sum\limits_{j=1}^k w_ix^{a_{i,j}},0\le a_{i,j} < 2^m\)，求其異或卷積。
顯然直接暴力有 \(nm2^m\)，或者簡單調(diào)整一下是 \((n+km)2^m\)。
考慮當 \(n\) 較大而 \(k\) 很小時，如 Triple，考慮一些更好的解法。
首先我們?nèi)菀装l(fā)現(xiàn)，考慮變換后的函數(shù)的 \(o\) 次項系數(shù) \(\widehat{f}=\sum_{i=1}^k s_{o,i}w_ix^o\) 我們的變換系數(shù) \(s\) 有 \(2^k\) 種取值，我們將其壓成 \(k\) 位二進制數(shù)，\(1\) 表示取 \(-1\)，\(0\) 表示取 \(i\)，后面就會發(fā)現(xiàn)這樣定義的深意，并設(shè) \(c_{Now,t}\) 表示狀態(tài)是 \(t\) 的次數(shù)。這里以及以后我們考慮當前是 \(Now\) 次項。
考慮 Triple 的解題過程，考慮枚舉 \(t< 2^k\)，即 \(t\) 是全集的子集，設(shè) \(z_{i}=\bigoplus_{j\in t} a_{i,j}\)，求 \(\sum\limits_{i=0}^{m} x^{z_{i}}\) 的變換，考慮其第 \(Now\) 項的總共 \(2^k\) 個值。
考慮到是線性變換，其第 \(i\) 實際上是求的 \(\sum FMT(x^{z_i})\)，考慮到每種 \(c\) 的情況對系數(shù)的貢獻，這個值顯然等于一些 \(c_i\) 有正有負的加起來。
考慮 \(c_i\) 前面的系數(shù)，\(z_{i}=\bigoplus_{j\in t} a_{i,j}\)，求 \(\sum\limits_{i=0}^{m} x^{z_{i}}\) 本質(zhì)是在求卷積，所以其相當于是單獨卷 \(a_{i,j}\) 的貢獻做點乘，簡單分析一下，當 \(t\) 的第 \(k\) 位是 \(1\) 且 \(i\) 的第 \(k\) 位也是 \(1\)（\(i\) 是狀壓的 \(s\)，而 \(i\) 的第 \(k\) 位是一意味著是負）的時候會有 \(-1\) 的貢獻，所以其系數(shù)是 \((-1)^{|t\&i|}\)。
發(fā)現(xiàn)這就是 XOR 變換的系數(shù)，于是我們將每個逆變換一下就知道次數(shù)了，最后快速冪即可，復(fù)雜度 \(n2^k+(m+k)2^{m+k}\)。
下面代碼實現(xiàn)了 $k=3$ 的 Triple，可以自行更改 $k$，注意要改值域
#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=1e5+3,MOD=998244353,Inv=(MOD+1)/2,M=17,K=3;
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,m,ck,h[1<<K|3][1<<M|3],sm[1<<K|3],c[N][K+3],tim[1<<M|3],cw[K+3],sw[1<<K|3],aas[1<<M|3];
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,int l,const function<void(int &,int &)> &F){for(int i=1;i<l;i<<=1) for(int j=0;j<l;++j) if(j&i) F(f[j^i],f[j]);}
const auto Xor=[](int &a,int &b){int t=a; a=Add(a,b),b=Sub(t,b);};
const auto IXr=[](int &a,int &b){int t=a; a=1ll*(a+b)*Inv%MOD,b=1ll*(t-b+MOD)*Inv%MOD;};
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m; ck=3;
for(int i=0;i<ck;++i) cin>>cw[i];
for(int i=0;i<1<<ck;++i) for(int j=0;j<ck;++j) sw[i]=(i>>j&1)?Sub(sw[i],cw[j]):Add(sw[i],cw[j]); // sw[i] 表示狀態(tài)是 i 的值。
for(int i=1;i<=n;++i){
for(int j=0;j<ck;++j) cin>>c[i][j];
++h[0][0]; for(int j=1;j<1<<ck;++j){int low=j&-j,p=__lg(low); ++h[j][sm[j]=sm[j^low]^c[i][p]];} // sm 是異或和，h 維護的是枚舉 t 后的多項式。
}
for(int i=0;i<1<<ck;++i) Fmt(h[i],1<<m,Xor); // 變換 h
for(int i=0;i<1<<m;++i){
for(int j=0;j<1<<ck;++j) tim[j]=h[j][i]; Fmt(tim,1<<ck,IXr); // 復(fù)制并做 IFMT
aas[i]=1; for(int j=0;j<1<<ck;++j) aas[i]=1ll*aas[i]*Fpw(sw[j],tim[j])%MOD; // 統(tǒng)計
}
Fmt(aas,1<<m,IXr); for(int i=0;i<1<<m;++i) cout<<aas[i]<<' ';
}
考慮做 OR 卷積，狀態(tài)設(shè)計和推導(dǎo)基本是一樣的，就是最后做逆變換是 AND 卷積的逆變換。
下面代碼實現(xiàn)了 OR 卷積，沒有題，但是和暴力在 $n\le 1000,m\le 10,k\le 10$ 值域在模數(shù)范圍內(nèi)的隨機數(shù)據(jù)過拍了，應(yīng)該不會錯
#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=1003,MOD=998244353,M=10,K=10;
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,m,ck,h[1<<K|3][1<<M|3],sm[1<<K|3],c[N][K+3],tim[1<<M|3],cw[K+3],sw[1<<K|3],aas[1<<M|3];
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,int l,const function<void(int &,int &)> &F){for(int i=1;i<l;i<<=1) for(int j=0;j<l;++j) if(j&i) F(f[j^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);},IAd=[](int &a,int &b){a=Sub(a,b);};
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>ck;
for(int i=0;i<ck;++i) cin>>cw[i];
for(int i=0;i<1<<ck;++i) for(int j=0;j<ck;++j) if(i>>j&1) sw[i]=Add(sw[i],cw[j]); // sw[i] 表示狀態(tài)是 i 的值。
for(int i=1;i<=n;++i){
for(int j=0;j<ck;++j) cin>>c[i][j];
++h[0][0]; for(int j=1;j<1<<ck;++j){int low=j&-j,p=__lg(low); ++h[j][sm[j]=sm[j^low]|c[i][p]];} // sm 是或和，h 維護的是枚舉 t 后的多項式。
}
for(int i=0;i<1<<ck;++i) Fmt(h[i],1<<m,Or); // 變換 h
for(int i=0;i<1<<m;++i){
for(int j=0;j<1<<ck;++j) tim[j]=h[j][i]; Fmt(tim,1<<ck,IAd); // 復(fù)制并做 IFMT，做的是 IAnd
aas[i]=1; for(int j=0;j<1<<ck;++j) aas[i]=1ll*aas[i]*Fpw(sw[j],tim[j])%MOD; // 統(tǒng)計
}
Fmt(aas,1<<m,IOr); for(int i=0;i<1<<m;++i) cout<<aas[i]<<' ';
}
AND 類似。
感覺可以上升到子集卷積，有時間在說吧。
P
本文來自博客園，作者：xrlong，轉(zhuǎn)載請注明原文鏈接：http://www.rzrgm.cn/xrlong/p/18535925
版權(quán)聲明：本作品采用 「署名-非商業(yè)性使用-相同方式共享 4.0 國際」許可協(xié)議（CC BY-NC-SA 4.0） 進行許可。
浙公網(wǎng)安備 33010602011771號