[真学习笔记] 前夕 - 单位根反演 - 广义容斥

51 阅读 0 评论 34 点赞

我是靠谱客的博主贪玩机器猫，最近开发中收集的这篇文章主要介绍[真学习笔记] 前夕 - 单位根反演 - 广义容斥，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这次是真的学习笔记了……
真正意义上搞明白广义容斥实在说啥……
真正搞明白了单位根的那个性质……

题目大意：有个大小为n的集合S，求所有选出若干非空且互不相等的子集使得交集大小是k的倍数。要求一个O(nk)的做法。
先来说说二项式反演这件事情：
$P(x)=sum_{k=0}^x Q(k)binom xk\Q(x)=sum_{k=0}^x P(k)binom xk (-1)^{x-k}$
这个显然是对的，因为你至少可以把互相带入……
知道了这件事情我们就可以去做一些广义容斥，例如，我们假定我们已经知道了P(k)表示大小至少k的答案，然后记Q(k)表示大小恰好k的答案，我们想通过P直接算出Q，也就是：
$Q(k)=sum_{i=0}^nP(i)f(i)$
也就是给P加一个系数f。
而左半部分就是下式，考虑一个大小是i的集合会被P(x)f(x)计算C(x, i)f(x)次：
$sum_{i=0}^nQ(i)sum_{j=0}^ibinom ij f(j)$
而我们最后希望这个东西是： $sum_{i=0}^nQ(i)[i==k]$
也就是 $sum_{i=0}^xbinom xif(i)=[x==k]$
我们把右边看做二项式反演的Q，那么有：
$f(x)=sum_{i=0}^x[i==k](-1)^{x-i}binom xi$
也就是当x< k时 $f (x) = 0$ 否则 $f(x)=(-1)^{x-k}binom{x}{k}$
这样就是常说的一种特殊形式的容斥。
这个题里面，显然取 $nxleft(2^{2^{n-k}}-1right)$
然后这里的 $[i = = k]$ 要变成 $[k ∣ i]$ ，也就是只对k的倍数那里统计。
然后就是单位根的性质：
$sum_{i=0}^{k-1}(w_k^n)^i$
单位根的一个应用是直接把 $w_k^i$ 这玩意带入到多项式里面，这样求和之后就只剩下k的倍数的项的系数的和的k倍了。
另一个就是直接展开，像这个题直接像上一个例子那样那[i==k]那里替换成[k|i]然后替换成上面单位根的式子然后推导一番即可。注意到交换求和顺序后（也就是先对不同的单位根求和再加起来）后面那一坨可以用二项式定理缩起来。
代码里面是假定k=4的题。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 10000010
#define lint long long
#define p 998244353
using namespace std;
inline int mol(lint x) { return x%=p,(x<0?x+p:x); }
int w[6],v[6],f[N],fi[N],a[N];
inline int fast_pow(int x,int k,int ans=1)
{	for(;k;k>>=1,x=(lint)x*x%p) (k&1)?ans=(lint)ans*x%p:0;return ans;	}
int main()
{
int n;scanf("%d",&n);
w[0]=1,w[1]=fast_pow(3,(p-1)/4),w[2]=(lint)w[1]*w[1]%p,w[3]=(lint)w[1]*w[2]%p;
w[1]=v[1]=mol(w[1]-1),w[2]=v[2]=mol(w[2]-1),w[3]=v[3]=mol(w[3]-1),f[0]=1,a[0]=2;
for(int i=1;i<=n;i++) f[i]=(lint)f[i-1]*i%p,a[i]=(lint)a[i-1]*a[i-1]%p;
fi[n]=fast_pow(f[n],p-2);
for(int i=n-1;i>=0;i--) fi[i]=fi[i+1]*(i+1ll)%p,a[i]=a[i]-1,(a[i]<0?a[i]+=p:0);
lint ans=4ll*a[n]*fi[n]%p;
for(int i=1;i<=n;i++)
ans+=(1ll*w[1]+w[2]+w[3])*fi[i]%p*fi[n-i]%p*a[n-i]%p,
w[1]=(lint)w[1]*v[1]%p,w[2]=(lint)w[2]*v[2]%p,w[3]=(lint)w[3]*v[3]%p;
return !printf("%lldn",(lint)mol(ans)*f[n]%p*fast_pow(4,p-2)%p);
}