初见安~首先讲一下前置知识吧。
一、单位根反演
先直接上公式吧：
考虑简单证明一下：
如果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——