初見安~首先講一下前置知識吧。
一、機關根反演
先直接上公式吧：
考慮簡單證明一下：
如果k是n的倍數，那麼根據機關根的性質，i*k一定也是n的倍數，那就是
，也就是n個1相加，再除以n就是1.
如果k不是n的倍數，那麼同理，後面就是一個等比數列求和了。可以發現收起來後分子為0。
再大概提一下應用。
比如目前我有一個多項式f，現在我要把為k的倍數的那些項的系數求和。那就是：
于是複雜度就從
降到
了。當k很小的時候就很友善。比如下面這個題。
二、題目
這裡是傳送門：LOJ#6358. 前夕
題解
題目描述真的是…啥都不說清楚。
題意是給你n個物品，可以有2^n種組合方案， 現在要求你選一些方案使得這些方案的交集的物品為4的倍數，問你有多少種選擇方案的方案。可以為空集。
考慮先欽定一部分一定選，設
表示交集中至少有k個物品的選擇方案數。則：
即：有2^{n-k}個集合一定包含了這k個物品，這些集合全都可選可不選。但是要除去空集，因為什麼都不選的話并沒有包含這k個物品，而且可能會在接下來的容斥中出問題。
好！到這裡我直接一發入魂開始寫廣義容斥定理了。（下文是我自己搞出來的nlogn的做法，不是正解，可以選擇性略過）
于是我設
表示交集中剛好有x個物品的方案數。則：
但是題意要求的是每一個
，或者說每一個x是4的倍數的
，直接搞複雜度就是n^2的。是以考慮多項式卷積一下：
後面就顯然是可以卷積的了。上NTT後複雜度
.
可是！n是1e7！！！這個log帶不動直接炸掉：）可以拿到70的部分分。
于是身心俱疲的我決定去看題解。
是以接下來就是正解了。（文末有廣義容斥搞的正解做法
廣義容斥有個很緻命的地方就是：
我是挨個挨個算的。如果我們不挨着算呢？
直接設最終的答案：
是我們強行構造上的一個容斥系數。于是我們考慮怎麼求這個東西。
其實可以大緻順延廣義容斥的思路，我們依舊設
表示交集恰好有x個物品的方案數。
廣義容斥的關系其實是由這個基本關系二項式反演後推出來的：
很好了解：至少x個，也就是說可以分為恰好x個，恰好x+1個……n個這些情況的和。
如果我們的答案是所有g的和，也就是g的每一項系數為1，而我們設定的容斥系數是跟着 f 的，那麼也就是說：我們希望在我們設定的容斥系數下，每個g(x)都恰好被累加到答案裡一次。
可以發現上面f和g的關系中，對于f，g的組合數是縱向的；而對于一個g在f中的貢獻就是橫向的了。一個f跟一個a，是以最後，一個g(x)在ans中的貢獻次數就是：
而我們實際期望的是：若x是4的倍數則為1， 否則為0。是以：
因為要求的是a，是以顯然二項式反演：
接下來就可以化左邊的式子來求a(x)了：
于是就已經可以求了。這裡機關根反演在取模意義下可以用原根代替。因為998244353的原根是3，對應了998244352個取值，是以要四等分的原根就是
。
到這裡就已經可以求了。注意快速幂的複雜度，這個題嚴格要求線性。
好了上代碼——
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 10000007
using namespace std;
typedef long long ll;
const int mx = 1e7, mod = 998244353, inv2 = 499122177, inv4 = 748683265;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
int fac[maxn], inv[maxn], w[4], n, a[maxn], f[maxn];
int C(int a, int b) {return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;}
int pw(int a, int b) {int res = 1; while(b) {if(b & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod, b >>= 1;} return res;}
signed main() {
fac[0] = inv[0] = 1;
for(int i = 1; i <= mx; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[mx] = pw(fac[mx], mod - 2);
for(int i = mx - 1; i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
w[1] = pw(3, (mod - 1) / 4); w[0] = 1;//w是原根。
for(int i = 2; i < 4; i++) w[i] = 1ll * w[i - 1] * w[1] % mod;
n = read();
int ans = 1;
f[n] = 2;//倒推，避免快速幂
for(int i = n - 1; i >= 0; i--) f[i] = 1ll * f[i + 1] * f[i + 1] % mod;
for(int i = 0; i <= n; i++) f[i] = 1ll * (1ll * f[i] - 1) * C(n, i) % mod;
for(int i = 0; i < 4; i++) {
register int tmp = 1;
for(int j = 0; j <= n; j++) a[j] = (a[j] + tmp) % mod, tmp = 1ll * tmp * (w[i] - 1) % mod;
}
for(int i = 0; i <= n; i++) {
ans = (ans + 1ll * a[i] * inv4 % mod * f[i] % mod) % mod;
}
printf("%d\n", ans);
return 0;
}
如果你上面的官方正解沒看懂，其實廣義容斥還是可以做出來的……：）【感謝機房神仙ptx
考慮用廣義容斥的話，變量名含義不變， 寫出來就該是這樣：
可以發現和我們上面退出來的東西是等價的。
迎評：）
——End——