再探 Triple——2025.8.28 鮮花

再探 Triple

寫完了，就提前發出來吧。

即刻輪回

いますぐ輪廻！！！
即刻輪回！！！
i ma su gu ri n ne
今回も結ばれないね…
這次也無法結合呢…
ko n ka i mo mu su ba re na i ne
噓ついたら針千本 誓って
發誓說謊就吞千根針
u so tsu i ta ra ha ri se n bo n chi ka tte
ぜったい來世でまた會お？
來世絕對要再相見 好嗎？
ze tta i ra i se de ma ta a o
いますぐ輪廻！！！
即刻輪回！！！
i ma su gu ri n ne
今回も結ばれないね…
這次也無法結合呢…
ko n ka i mo mu su ba re na i ne
全て 捨てて
全部丟棄
su be te su te te
「さらば 生まれ変わる」
「再見了 轉世重生」
sa ra ba u ma re ka wa ru
「あまりに人生が 憂い」
「人生實在是過于 憂傷」
a ma ri ni ji n se i ga u re i
「君の指輪も白紙になって！」
「連你的戒指也變白紙了啊！」
ki mi no yu bi wa mo ha ku shi ni na tte
「せんぶ消えちゃって、
「全部消失
se n bu ki e cha tte
いいよ
也無妨
i i yo
「どうせ生まれ変わって」
「反正還能重生」
do u se u ma re ka wa tte
「巡って 出會って」
「輪回到再次相遇」
me gu tte de a tte
「宇宙が爆ぜてしまうまで」
「直至宇宙爆炸」
u chu u ga ha ze te shi ma u ma de
「何回も大好きになって」
「無數次愛上你」
na n ka i mo da i su ki ni na tte
「何回も大好きになって」
「無數次愛上你」
na n ka i mo da i su ki ni na tte
「毎回繰り返す身勝手」
「輪回往復的自私」
ma i ka i ku ri ka e su mi ga tte
「何回も大好きになって」
「無數次愛上你」
na n ka i mo da i su ki ni na tte
「ごめんね」
「對不起吶」
go me n ne
「メタモルフォーゼ」
「變身」
me ta mo ru fo o ze
いますぐ輪廻！！！
即刻輪回！！！
i ma su gu ri n ne
今回も結ばれないね★
這次也無法結合呢★
ko n ka i mo mu su ba re na i ne
噓ついたら針千本 誓って
發誓說謊就吞千根針
u so tsu i ta ra ha ri se n bo n chi ka tte
ぜったい來世でまた會お★
來世絕對要再相見 好嗎★
ze tta i ra i se de ma ta a o
いますぐ輪廻！！！
即刻輪回！！！
i ma su gu ri n ne
今回も結ばれないね★
這次也無法結合呢★
ko n ka i mo mu su ba re na i ne
全て 捨てて ぽいっ★
全部丟棄（丟）★
su be te su te te po i tsu
「だから 生まれ変われ」
「所以啊 轉世重生吧」
da ka ra u ma re ka wa re
「間違った人生は 憂い」
「錯誤的人生只有 憂傷」
ma chi ga tta ji n se i wa u re i
「君の隣は私になって？」
「你身邊的位置可以替換成我嗎？」
ki mi no to na ri wa wa ta shi ni na tte
運命よ 跪け
命運啊 給我跪下
u n me i yo hi za ma zu ke
「いますぐ輪廻 今回も結ばれないね」
「即刻輪回 這次也無法結合呢」
i ma su gu ri n ne ko n ka i mo mu su ba re na i ne
「いますぐ輪廻 今回は報われないね」
「即刻輪回 這次也無法得償所愿呢」
i ma su gu ri n ne ko n ka i wa mu ku wa re na i ne
「全て 捨てて
「全部丟棄
su be te su te te
いますぐしんで！
現在就去死吧！
i ma su gu shi n de
「ファンファーレが鳴って」
「號角聲鳴」
fa n fa a re ga na tte
「大正解、おめでとう！」
「完全正確 恭喜你！」
da i se i ka i o me de to u
「ようやく君は救われる」
「你終于被拯救」
yo u ya ku ki mi wa su ku wa re ru
「來世でまた會おう★」
「來世再相見吧★」
ra i se de ma ta a o u
「いますぐ輪廻」
「即刻輪回」
i ma su gu ri n ne
「ちょっと苦しんで」
「稍微受點苦」
cho tto ku ru shi n de
「ツインレイなんだよ？！？！」
「我們可是雙生火焰哦？！？！」
tsu i n re i na n da yo
早く
快點
ha ya ku
ねぇ
吶
ne e
「私と一つになろう」
「來和我合為一體吧」
wa ta shi to hi to tsu ni na ro u
「さぁ魂の浄化」
「來吧 讓靈魂得到凈化」
sa a ta ma shi i no jo u ka
「死への調和」
「與死亡的調和」
shi e no cho u wa
「どうか光になって」
「請化作光輝吧」
do u ka hi ka ri ni na tte
全て捨てて
全部丟棄
su be te su te te
「ぽいっ」
「（丟）」
po i tsu

很久以前有一篇鮮花寫了 Triple 擴展，但當時我太菜了，寫的啥也不是。

只能說 Triple 還是太牛了。

首先我們知道一下 FWT 變換一些基本知識。在「快速數列變換這個詞怎么造出來的」的一些閱讀感悟中我們已經提到過了，我們現在沒有很好的適配最新張量做法的 Triple 做法，所以我們依然使用 \(c_{i, j} c_{i, k} = c_{i, j \circ k}\) 這個矩陣。

這里區分一下，定義 \(c'\) 表示 \(c\) 按位拆開后的位矩陣，有 \(c = \prod c'\)。

考慮一下 Triple 的流程，以下下標從 \(0\) 開始：

首先我們要求的是 \([x^p] \prod_i \sum_j c_{p, a_{i, j}} d_j\)。

我們顯然是要把它拆開的，注意到 \(c\) 的值域很小，所以在一個 \(\sum\) 中 \(c_{p, a_{i, j}}\) 組成的序列只有 \(2^m\) 種可能，我們希望求出每種的出現次數。

先狀壓一下，這里若是按照大多數題解的做法的狀壓方法雖然會簡單，但是不利于展現其普適性，我們這里采用二進制數 \(s\) 的第 \(p\) 位 \(s_p = 1\) 表示 \(c_{p, a_{i, p}} = 1\)，\(s_p = 0\) 表示 \(c_{p, a_{i, p}} = -1\)。

設 \(t_s\) 表示 \(s\) 這種狀態的出現次數，我們希望解出 \(t_s\)，自然需要方程。

枚舉 \(T \subseteq \{0, 1, \dots, m - 1\}\)，將 \(z_{i} = \bigoplus_{j \in t} a_{i, j}\) 求 \({\rm FWT}(\sum_i x^{z_i})\)，有 \([x^p]{\rm FWT}(\sum_i x^{z_i}) = \sum_i c_{p, z_i}\)，將 \(c_{i, j} c_{i, k} = c_{i, j \circ k}\) 帶入有 \(\sum_i c_{p, z_i} = \sum_i\prod_{j \in T} c_{p, a_{i, j}}\)。

感覺上這個已經和 \(t\) 有了千絲萬縷的聯系，考慮將其聯系起來，容易發現其滿足 \(\sum_i\prod_{j \in T} c_{p, a_{i, j}} = \sum_s f_{p, s}t_s\)，這里 \(f_{p, s}\) 是一個貢獻系數矩陣。

我們發現 \(\sum_s f_{p, s}t_s\) 和 FWT 的變換有著千絲萬縷的聯系，我們發現這個 \(f\) 竟然也是位矩陣，于是我們直接按位考慮將 \(f\) 拆成 \(f'\)，將 \(f'\) 求逆做 IFWT 即可。

考慮這個流程可以做哪些運算，我們發現我們用到的性質只有 \(c_{i, j} c_{i, k} = c_{i, j \circ k}\) 和 \(c\) 的值域很小，并且 \(f'\) 得有逆。雖然我沒仔細考慮，但感覺上 \(f'\) 有逆這個限制很容易滿足，難點還是構造 \(c\)，感覺是能擴展到一部分運算的。

給個【UNR #2】黎明前的巧克力的代碼：

Code

/*
ulimit -s 1024000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra && ulimit -v 128000 && ./%<
ulimit -s 1024000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -fsanitize=address,undefined -g && ./%<
echo && cat out.out && echo
*/
#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.in", "r", stdin), *OutFile = freopen("out.out", "w", stdout);
__attribute__((destructor)) void End_Put(){
	cerr << "\nTime:       " << clock() / 1000000. << "s\n";
	assert(!system("grep VmPeak /proc/$PPID/status 1>&2"));
}
#endif

const int N = 1e6 + 3, M = 1 << 20 | 3, K = 2, MOD = 998244353, I2 = (MOD + 1) >> 1;
int Fpw(int a, int b){ int r = 1; for(; b; a = 1ll * a * a % MOD, b >>= 1) if(b & 1) r = 1ll * r * a % MOD; return r; }
int n, ck = 2, _a[N], ca[N][K], cd[K], sd[1 << K], ch[1 << K][M], sm[1 << K], tp[1 << K], aas[M];

void Fwt(int *f, int l, auto F){
	for(int k = 1; k < l; k <<= 1)
		for(int i = 0; i < l; i += (k << 1)) for(int j = 0; j < k; ++j)
			F(f[i + j], f[i + j + k]);
}
void Xor(int &a, int &b){ tie(a, b) = make_pair((a + b) % MOD, (a - b) % MOD); }
void Ixr(int &a, int &b){ tie(a, b) = make_pair(1ll * (a + b) * I2 % MOD, 1ll * (a - b) * I2 % MOD); }

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n; cd[0] = 1, cd[1] = 2;
	int _l = 1 << 20, _s = 1 << ck;
	for(int s = 0; s < _s; ++s) for(int i = 0; i < ck; ++i) sd[s] += (s >> i & 1) ? -cd[i] : cd[i];
	for(int i = 1; i <= n; ++i) cin >> ca[i][1], ca[i][0] = 0;
	for(int i = 1; i <= n; ++i){
		++ch[0][0];
		for(int s = 1, _; s < _s; ++s) 
			++ch[s][sm[s] = sm[s ^ (s & -s)] ^ ca[i][__builtin_ctz(s)]];
	}
	for(int i = 0; i < _s; ++i) Fwt(ch[i], _l, Xor);
	for(int i = 0; i < _l; ++i){
		for(int s = 0; s < _s; ++s) tp[s] = ch[s][i];
		Fwt(tp, _s, Ixr); int &ans = aas[i] = 1;
		for(int s = 0; s < _s; ++s) ans = 1ll * ans * Fpw(sd[s], tp[s]) % MOD;
	}
	Fwt(aas, _l, Ixr);
	cout << (aas[0] - 1 + MOD) % MOD;
}

posted @ 2025-08-27 17:46 xrlong 閱讀(89) 評論(2) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

再探 Triple——2025.8.28 鮮花

再探 Triple

公告

Loading