本文共 1714 字,大约阅读时间需要 5 分钟。
题意
给定函数 F ( a ) , G ( b ) , H ( c ) F(a),G(b),H(c) F(a),G(b),H(c),分别返回 f , g , h f,g,h f,g,h数组的第 a , b , c a,b,c a,b,c项(从零起)
求 R [ l ] = ∑ F ( a ) ∗ G ( b ) ∗ H ( c ) R[l]=\sum F(a)*G(b)*H(c) R[l]=∑F(a)∗G(b)∗H(c)
其中满足 ( a ∣ b ∣ c ) & l = = l (a|b|c)\&l==l (a∣b∣c)&l==l
首先我们可以用 S O S D P SOSDP SOSDP快速求 R [ l ] = ∑ a & l = = l F ( a ) R[l]=\sum\limits_{a\&l==l}F(a) R[l]=a&l==l∑F(a)
让我们试着来求一个 W ( i ) = ∑ ( a ∣ b ∣ c ) = = i F ( a ) ∗ G ( b ) ∗ H ( c ) W(i)=\sum\limits_{(a|b|c)\ ==i}F(a)*G(b)*H(c) W(i)=(a∣b∣c) ==i∑F(a)∗G(b)∗H(c)
那么其实答案就是 R ( l ) = ∑ l & i = = l W ( i ) R(l)=\sum\limits_{l\&i==l}W(i) R(l)=l&i==l∑W(i)
然后一遍 S O S D P SOSDP SOSDP即可得出解,问题在于我们似乎无法处理出这样的 F G FG FG
哦,抱歉,说错了, W ( i ) W(i) W(i)其实是一个或卷积的形式,只需要用 F W T FWT FWT即可快速得到解^_^
#includeusing namespace std;#define int long longconst int N = (1<<21),mod = 1e9+7;int n,mx,F[N],G[N],H[N],ans;void OR(int f[],int type){ for(int mid=2,k=1;mid<=mx;mid<<=1,k<<=1) for(int i=0;i =0;j--) if( !(j&(1<
然后其实也可以不用 F W T FWT FWT
观察到求 R [ l ] = ∑ F ( a ) ∗ G ( b ) ∗ H ( c ) R[l]=\sum F(a)*G(b)*H(c) R[l]=∑F(a)∗G(b)∗H(c)
考虑每一个三元组 ( a , b , c ) (a,b,c) (a,b,c)的贡献,会贡献所有是 a ∣ b ∣ c a|b|c a∣b∣c的子集的 l l l
但是这样太慢,所以我们考虑把 a ∣ b ∣ c a|b|c a∣b∣c相等的三元组放一起算贡献
把 F , G , H F,G,H F,G,H都做一遍 S O S D P SOSDP SOSDP然后累乘得到 W ( i ) W(i) W(i)
现在 W ( i ) W(i) W(i)表示的是所有 a ∣ b ∣ c a|b|c a∣b∣c是 i i i子集的权值和
为了得到 W ( i ) W(i) W(i)表示 a ∣ b ∣ c = = i a|b|c==i a∣b∣c==i的权值和
我们倒着做 S O S D P SOSDP SOSDP,也就是把之前的加变成减
于是得到 W ( i ) W(i) W(i)表示 a ∣ b ∣ c a|b|c a∣b∣c是 i i i的权值和
下面有两种计算方式,一是和上面做法一样去做一遍子集 S O S D P SOSDP SOSDP
或者容斥,因为三元组或为 x x x的贡献次数是所有 x x x的子集
所以 x x x贡献 2 d ( x ) 2^{d(x)} 2d(x)次
这里的贡献包含了 x x x子集的贡献,所以可以根据 1 1 1的个数来容斥
挂个别人的代码,不想写了,思维很巧妙,做法很复杂
转载地址:https://issue-is-vegetable.blog.csdn.net/article/details/112798523 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!