#33864: 位元卷積
M_theory
(Bell Inequality)
學校
:
臺北市私立延平高級中學
編號 : 83305
來源 : [61.231.4.25]
最後登入時間 ：
2024-03-14 23:19:13
i229. XOR
| From: [1.34.159.245] |
發表日期
:
2023-02-09 22:50
題目給的N可以到2^20(=1e6)，如果直接暴力乘開會TLE。
作法：將輸入的數列a和b分別FWT之後分別相乘，再逆轉換回去就可以得到所求。時間複雜度$O(N log N)$。（詳細作法可以上網搜尋fast Walsh–Hadamard transform）
注意要用__int128_t，不然會overflow。
#33888: Re: 位元卷積
M_theory
(Bell Inequality)
學校
:
臺北市私立延平高級中學
編號 : 83305
來源 : [61.231.4.25]
最後登入時間 ：
2024-03-14 23:19:13
i229. XOR
| From: [1.34.159.245] |
發表日期
:
2023-02-10 23:30
題目給的N可以到2^20(=1e6)，如果直接暴力乘開會TLE。
作法：將輸入的數列a和b分別FWT之後分別相乘，再逆轉換回去就可以得到所求。時間複雜度$O(N log N)$。（詳細作法可以上網搜尋fast Walsh–Hadamard transform）
注意要用__int128_t，不然會overflow。
更正：可以不用__int128_t，一邊計算一邊取模就可以。只是在逆轉換時/2要改成*2的模逆元
ZeroJudge Forum