网站建设的类型或分类,文章类网站模板,wordpress 图集,优秀企业简介100字时隔一年再回首FWT#xff0c;我似乎有了新理解#xff1f;#xff1f; 添加了原理的推导#xff0c;以前就只有模板… 文章目录引入or#xff08;或#xff09;卷积原理FWT_or正变换FWT_or逆变换模板and#xff08;与#xff09;卷积原理FWT_and正变换FWT_and逆变换模… 时隔一年再回首FWT我似乎有了新理解 添加了原理的推导以前就只有模板… 文章目录引入or或卷积原理FWT_or正变换FWT_or逆变换模板and与卷积原理FWT_and正变换FWT_and逆变换模板xor异或卷积原理FWT_xor正变换FWT_xor逆变换模板例题T1Card GameT2Tree Cutting引入 第一次学习的时候因为连FFTFFTFFT都没学懂 所以当时学FWTFWTFWT加之是在家里网课 就直接掉线无法连回——一直都是背板子是完全没学懂啊 最近重新学习了一遍就马上来完善一下只有模板的博客
学了FFTFFTFFT我们知道是可以用来算多项式乘法的 h(x)∑ijxf(i)×g(j)h(x)\sum_{ijx}f(i)\times g(j)h(x)ijx∑f(i)×g(j) 但是可不可以算其他的改变i,ji,ji,j之间的关系限制呢 {h(x)∑i∣jxf(i)×g(j)h(x)∑ijxf(i)×g(j)h(x)∑i⊕jxf(i)×g(j)\left\{ \begin{aligned} h(x)\sum_{i|jx}f(i)\times g(j)\\ h(x)\sum_{i\jx}f(i)\times g(j)\\ h(x)\sum_{i⊕jx}f(i)\times g(j)\\ \end{aligned} \right.⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧h(x)i∣jx∑f(i)×g(j)h(x)ijx∑f(i)×g(j)h(x)i⊕jx∑f(i)×g(j) |表示二进制或运算表示二进制与运算⊕表示二进制异或运算
怎么做呢——还是按着FFTFFTFFT的思路来 考虑能不能将多项式转化一下变成位对位相乘最后转化回去就是所求多项式 这就是FWTFWTFWT完成的使命了 前人已经找到了规律备矣我只是记录规律的正确性 因为模仿FFT所以n应该也为2的幂下文意义默认为2的幂 or或卷积
原理
求 h(x)∑i∣jxf(i)×g(j)h(x)\sum_{i|jx}f(i)\times g(j)h(x)i∣jx∑f(i)×g(j) 定义多项式AAA转化规律A′[i]∑ijiA[j]A[i]\sum_{i\ji} A[j]A′[i]iji∑A[j] h′[y]∑xyxh[x]h[y]\sum_{x\ yx}h[x]h′[y]xyx∑h[x]∑xyx∑i∣jxf[i]×g[j]\sum_{x\ yx}\sum_{i|jx}f[i]\times g[j]xyx∑i∣jx∑f[i]×g[j] i|jx表明i,j都是x的子集而x又是y子集⇒\Rightarrow⇒i,j是y的子集 ∑iyi∑jyjf[i]×g[j]\sum_{i\yi}\sum_{j\yj}f[i]\times g[j]iyi∑jyj∑f[i]×g[j](∑iyif[i])×(∑jyjg[j])(\sum_{i\yi}f[i] )\times(\sum_{j\yj}g[j])(iyi∑f[i])×(jyj∑g[j])f′[y]×g′[y]f[y]\times g[y]f′[y]×g′[y] 成功实现位对位相乘yeah举国同庆 最近重温FFT,NTTFFT,NTTFFT,NTT竟然变成了懂原理看代码看半天 所以接下来说一下实现思路是递归写法是递推都好懂
FWT_or正变换
考虑模仿FFTFFTFFT也是不断/2/2/2将时间复杂度降下去 设yn2y\frac{n}{2}y2n则有 h′[y]∑xyxf[x]×g[x]h[y]\sum_{x\ yx}f[x]\times g[x]h′[y]xyx∑f[x]×g[x] h′[yn2]∑x(yn2)xf[x]×g[x]h[y\frac{n}{2}]\sum_{x\(y\frac{n}{2})x}f[x]\times g[x]h′[y2n]x(y2n)x∑f[x]×g[x] 将h′[yn2]h[y\frac{n}{2}]h′[y2n]的子集xxx拆分成两类分别考虑 ①xn2x\frac{n}{2}x2n即二进制最高位是000则有xyx(yn2)x\ yx\(y\frac{n}{2})xyx(y2n) ∑xyxf[x]×g[x]h′[y]\sum_{x\yx}f[x]\times g[x]h[y]xyx∑f[x]×g[x]h′[y] ②xn2x\frac{n}{2}x2n ∑x(yn2)f[x]×g[x]\sum_{x\(y\frac{n}{2})}f[x]\times g[x]x(y2n)∑f[x]×g[x] 将情况②当成新的多项式继续往下FWTFWTFWT长度砍掉一半循环上面的操作 最后要将左半部分的答案加到右半部分 不断往下然后把左边蓝色计算出来再加给右边红色从下往上递推
FWT_or逆变换
就是从上往下先减掉再往下
模板
opt1opt1opt1是正变换
void FWT_or( int *v, int f ) {for( int i 1;i n;i 1 )for( int j 0;j n;j ( i 1 ) )for( int k 0;k i;k )v[i j k] ( v[i j k] f * v[j k] ) % mod;
}and与卷积
原理
问 h(x)∑ijxf(i)×g(j)h(x)\sum_{i\jx}f(i)\times g(j)h(x)ijx∑f(i)×g(j) 定义多项式变换规律 A′[i]∑ijiA[j]A[i]\sum_{i\ji}A[j]A′[i]iji∑A[j] h′[y]∑xyyh[x]h[y]\sum_{x\yy}h[x]h′[y]xyy∑h[x]∑xyy∑ijxf[i]×g[j]\sum_{x\yy}\sum_{i\jx}f[i]\times g[j]xyy∑ijx∑f[i]×g[j] ijx说明x是i,j的子集而y又是x的子集⇒\Rightarrow⇒y是i,j的子集 ∑iyy∑jyyf[i]×g[j]\sum_{i\yy}\sum_{j\yy}f[i]\times g[j]iyy∑jyy∑f[i]×g[j](∑iyyf[i])×(∑jyyg[j])(\sum_{i\yy}f[i])\times (\sum_{j\yy}g[j])(iyy∑f[i])×(jyy∑g[j])f′[y]×g′[y]f[y]\times g[y]f′[y]×g′[y]
FWT_and正变换
与FWT_or差不多的思路 设y≥n2y\ge \frac{n}{2}y≥2n h′[y]∑xyyf[x]×g[x]h[y]\sum_{x\yy}f[x]\times g[x]h′[y]xyy∑f[x]×g[x] h′[y−n2]∑x(y−n2)(y−n2)f[x]×g[x]h[y-\frac{n}{2}]\sum_{x\(y-\frac{n}{2})(y-\frac{n}{2})}f[x]\times g[x]h′[y−2n]x(y−2n)(y−2n)∑f[x]×g[x] 同样的将h′[y−n2]h[y-\frac{n}{2}]h′[y−2n]符合条件的xxx分成两类来考虑 ①x≥n2x\ge \frac{n}{2}x≥2n 说明xxx最高位是111 不考虑xxx的最高位后y−n2y-\frac{n}{2}y−2n仍是其子集 那么yyy也是xxx的子集 ∑xyyf[x]×g[x]h′[y]\sum_{x\yy}f[x]\times g[x]h[y]xyy∑f[x]×g[x]h′[y] ②xn2x\frac{n}{2}x2n ∑x(y−n2)(y−n2)f[x]×g[x]\sum_{x\(y-\frac{n}{2})(y-\frac{n}{2})}f[x]\times g[x]x(y−2n)(y−2n)∑f[x]×g[x] 将此情况当成新的多项式继续往下求解 从下往上算完后将右半部分红色加到左半部分蓝色里再往上回溯
FWT_and逆变换
从上往下先左减去右再下放
模板
void FWT_and( int *v, int f ) {for( int i 1;i n;i 1 )for( int j 0;j n;j ( i 1 ) )for( int k 0;k i;k )v[j k] ( v[j k] v[j k i] * f ) % mod;
}xor异或卷积 原理
问 h(x)∑i⊕jxf(i)×g(j)h(x)\sum_{i⊕jx}f(i)\times g(j)h(x)i⊕jx∑f(i)×g(j) 定义多项式变换规律 A′[i]∑cnt(ij1)%20A[j1]−∑cnt(ij2)%21A[j2]A[i]\sum_{cnt(i\j_1)\%20}A[j_1]-\sum_{cnt(i\j_2)\%21}A[j_2]A′[i]cnt(ij1)%20∑A[j1]−cnt(ij2)%21∑A[j2] cnt(i)cnt(i)cnt(i)表示iii二进制有多少个111 h′[y]∑cnt(yx1)%20h[x1]−∑cnt(yx2)%21h[x2]h[y]\sum_{cnt(y\x_1)\%20}h[x_1]-\sum_{cnt(y\x_2)\%21}h[x_2]h′[y]cnt(yx1)%20∑h[x1]−cnt(yx2)%21∑h[x2]∑cnt(yx1)%20∑i1⊕j1x1f[i1]×g[j1]−∑cnt(yx2)%21∑i2⊕j2x2f[i2]×g[j2]\sum_{cnt(y\x_1)\%20}\sum_{i_1⊕j_1x_1}f[i_1]\times g[j_1]-\sum_{cnt(y\x_2)\%21}\sum_{i_2⊕j_2x_2}f[i_2]\times g[j_2]cnt(yx1)%20∑i1⊕j1x1∑f[i1]×g[j1]−cnt(yx2)%21∑i2⊕j2x2∑f[i2]×g[j2] 似乎卡住了推不下去了这可不行证明不了正确性啊 那没办法了正着推不下去老子倒着往回退可还行 仗着前人的正确性疯狂整 f′[x]×g′[x]f[x]\times g[x]f′[x]×g′[x](∑f[i]−∑f[j])×(∑g[i]−∑g[j])(\sum f[i]-\sum f[j])\times (\sum g[i]-\sum g[j])(∑f[i]−∑f[j])×(∑g[i]−∑g[j])cnt(xi)%20,cnt(xj)%21cnt(x\ i)\%20,cnt(x\j)\%21cnt(xi)%20,cnt(xj)%21∑f[i]g[i]∑f[j]g[j]−∑f[i]g[j]−∑f[j]g[i]\sum f[i]g[i]\sum f[j]g[j]-\sum f[i]g[j]-\sum f[j]g[i]∑f[i]g[i]∑f[j]g[j]−∑f[i]g[j]−∑f[j]g[i] 这里需要抽象理解式子才能建立关联发现与h′[x]h[x]h′[x]展开是一致的 不好意思我太菜了建立不了关联——那就换一种证法 x(i⊕j)≡xixj(mod2)x\(i⊕j)\equiv x\ ix\j\ \ \ \ (mod\ \ \ 2)x(i⊕j)≡xixj (mod 2) 我们采取暴力分类讨论智障求证下面i,j,x均表示其二进制某一位上为1/01/01/0 i1,j1,x0 i⊕j0,(i⊕j)x0i⊕j0,(i⊕j)\x0i⊕j0,(i⊕j)x0 xi0,xj0,xixj0x\i0,x\j0,x\ix\j0xi0,xj0,xixj0i0,j0,x0 i⊕j0,(i⊕j)x0i⊕j0,(i⊕j)\x0i⊕j0,(i⊕j)x0 xi0,xj0,xixj0x\i0,x\j0,x\ix\j0xi0,xj0,xixj0i1,j0,x0 i⊕j1,(i⊕j)x0i⊕j1,(i⊕j)\x0i⊕j1,(i⊕j)x0 xi0,xj0,xixj0x\i0,x\j0,x\ix\j0xi0,xj0,xixj0i0,j1,x0 i⊕j1,(i⊕j)x0i⊕j1,(i⊕j)\x0i⊕j1,(i⊕j)x0 xi0,xj0,xixj0x\i0,x\j0,x\ix\j0xi0,xj0,xixj0i0,j0,x1 i⊕j0,(i⊕j)x0i⊕j0,(i⊕j)\x0i⊕j0,(i⊕j)x0 xi0,xj0,xixj0x\i0,x\j0,x\ix\j0xi0,xj0,xixj0i0,j1,x1 i⊕j1,(i⊕j)x1i⊕j1,(i⊕j)\x1i⊕j1,(i⊕j)x1 xi0,xj1,xixj1x\i0,x\j1,x\ix\j1xi0,xj1,xixj1i1,j0,x1 i⊕j1,(i⊕j)x1i⊕j1,(i⊕j)\x1i⊕j1,(i⊕j)x1 xi1xj0,xixj1x\i1x\j0,x\ix\j1xi1xj0,xixj1i1,j1,x1 i⊕j0,(i⊕j)x0i⊕j0,(i⊕j)\x0i⊕j0,(i⊕j)x0 xi1,xj1,xixj2x\i1,x\j1,x\ix\j2xi1,xj1,xixj2 此情况注意是在取模2下所以奇偶还是没变 将A′AA′换一种表达方式 A′[i]∑(−1)cnt(ij)%2A[j]A[i]\sum (-1)^{cnt(i\j)\% 2}A[j]A′[i]∑(−1)cnt(ij)%2A[j] 重新推一遍式子 科研就是不断失败重头再来 h′[y]∑(−1)cnt(yx)%2h[x]∑(−1)cnt(yx)%2∑i⊕jxf[i]g[j]h[y]\sum(-1)^{cnt(y\x)\%2}h[x]\sum(-1)^{cnt(y\x)\%2}\sum_{i⊕jx}f[i]g[j]h′[y]∑(−1)cnt(yx)%2h[x]∑(−1)cnt(yx)%2i⊕jx∑f[i]g[j]∑(−1)cnt(y(i⊕j))%2f[i]g[j]∑(−1)cnt(yi)cnt(yj)f[i]g[j]\sum (-1)^{cnt(y\(i⊕j))\%2}f[i]g[j]\sum (-1)^{cnt(y\i)cnt(y\j)}f[i]g[j]∑(−1)cnt(y(i⊕j))%2f[i]g[j]∑(−1)cnt(yi)cnt(yj)f[i]g[j]∑(−1)cnt(yi)f[i]×∑(−1)cnt(yj)g[j]\sum (-1)^{cnt(y\i)}f[i]\times \sum (-1)^{cnt(y\j)}g[j]∑(−1)cnt(yi)f[i]×∑(−1)cnt(yj)g[j]f′[y]×g′[y]f[y]\times g[y]f′[y]×g′[y] FWT_xor正变换
有了前面两种简单的铺垫这里的思路是一致的不再写式子
当yn2y\frac{n}{2}y2n 将符合条件的xxx同样分成两类 ①xn2x\frac{n}{2}x2n ②x≥n2x\ge \frac{n}{2}x≥2n xyx\yxy的111个数的奇偶性并没有发生改变 直接加起来
当y≥n2y\ge \frac{n}{2}y≥2n 将符合条件的xxx同样分成两类 ①xn2x\frac{n}{2}x2n ②x≥n2x\ge \frac{n}{2}x≥2n 情况②的xyx\yxy最高位为111个数奇偶性发生改变前面带的符号变成负号 FWT(A)(FWT(B)FWT(C)FWT(B)−FWT(C))FWT(A)(FWT(B)FWT(C)FWT(B)-FWT(C))FWT(A)(FWT(B)FWT(C)FWT(B)−FWT(C))
FWT_xor逆变换
就相当于解一个二元一次方程已知和差 IFWT(A)(IFWT(B)IFWT(C)2,IFWT(B)−IFWT(C)2)IFWT(A)(\frac{IFWT(B)IFWT(C)}{2},\frac{IFWT(B)-IFWT(C)}{2})IFWT(A)(2IFWT(B)IFWT(C),2IFWT(B)−IFWT(C))
模板
void FWT_xor( int *v, int f ) {for( int i 1;i n;i 1 )for( int j 0;j n;j ( i 1 ) ) for( int k 0;k i;k ) {int x v[j k], y v[j k i];v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;if( f -1 ) {v[j k] v[j k] * inv % mod;v[j k i] v[j k i] * inv % mod;}}
}例题 听得懂原理理解记忆模板 听不懂强化训练 T1Card Game
title Alice and Bob now love to play a card game. Everyone is starting n cards, each card has no more than m attribute. Now they need finish Q tasks, each task will require everyone to give a card, and then make up the attribute types that the task demands (e.g. the task required attributes A, B, C, Alice’s card contains A B and Bob’s card contains B, C. they can use this union to finish the task). For each task, How many ways that Alice and Bob can do this task. Input here are T cases. (T20) (about 5 test cases n1000 m12 Q1000) For each test case.The first line contains two integers n,mn100000, m18, which indicates the number of cards which each one has and total attributes. The next line contain n binary numbers indicates the cards Alice has. The ith binary number m_i indicates the attributes each card have. (m_i 2^18) if m_i 10011 , this card has the first, second and fifth attrtbutes he next line contain n binary numbers indicates the cards Bob has. Then contain one integer Q which is the number of Tasks. Then next Q lines, each contain one binary number q_i which indicates the attributes they need to make. qi 2^18 Output For each test case, you first output one line “Case #%d:” Then output q lines, each line contains one which indicates the ways they can finish this task. Sample Input
1
4 4
1001 11 1100 1000
1110 1001 10 100
2
1100
111Sample Output
Case #1:
2
1solution 板题就是套FWT_orFWT\_orFWT_or code
#include cstdio
#include cstring
#define mod 998244353
#define MAXN 200000
int n, m, N, Q;
long long A[MAXN], B[MAXN], v[MAXN], c[MAXN];
long long inv ( mod 1 ) 1;
char s[30];long long read() {scanf( %s, s );int len strlen( s );long long x 0;for( int i 0;i len;i )x ( x 1 ) ( s[i] - 0 );return x;
}void FWT_or( long long *v, int opt ) {for( int i 2;i N;i 1 )for( int p i 1, j 0;j N;j i )for( int k j;k j p; k )v[k p] v[k] * opt;
}int main() {int T, n, m;scanf( %d, T );for( int t 1;t T;t ) {printf( Case #%d:\n, t );scanf( %d %d, n, m );N 1 m;memset( A, 0, sizeof( A ) );memset( B, 0, sizeof( B ) );for( int i 1;i n;i ) A[read()] ;for( int i 1;i n;i ) B[read()] ;FWT_or( A, 1 ), FWT_or( B, 1 );for( int i 0;i N;i )A[i] A[i] * B[i];FWT_or( A, -1 );scanf( %d, Q );while( Q -- ) printf( %lld\n, A[read()] );}return 0;
}T2Tree Cutting
title Byteasar has a tree TTT with nnn vertices conveniently labeled with 1,2,...,n1,2,...,n1,2,...,n. Each vertex of the tree has an integer value viv_ivi. The value of a non-empty tree TTT is equal to v1⊕v2⊕...⊕vnv_1\oplus v_2\oplus ...\oplus v_nv1⊕v2⊕...⊕vn, where ⊕\oplus⊕ denotes bitwise-xor. Now for every integer kkk from [0,m)[0,m)[0,m), please calculate the number of non-empty subtree of TTT which value are equal to kkk. A subtree of TTT is a subgraph of TTT that is also a tree. Input The first line of the input contains an integer T(1≤T≤10)T(1\leq T\leq10)T(1≤T≤10), denoting the number of test cases. In each test case, the first line of the input contains two integers n(n≤1000)n(n\leq 1000)n(n≤1000) and m(1≤m≤210)m(1\leq m\leq 2^{10})m(1≤m≤210), denoting the size of the tree TTT and the upper-bound of vvv. The second line of the input contains nnn integers v1,v2,v3,...,vn(0≤vim)v_1,v_2,v_3,...,v_n(0\leq v_i m)v1,v2,v3,...,vn(0≤vim), denoting the value of each node. Each of the following n−1n-1n−1 lines contains two integers ai,bia_i,b_iai,bi, denoting an edge between vertices aia_iai and bi(1≤ai,bi≤n)b_i(1\leq a_i,b_i\leq n)bi(1≤ai,bi≤n). It is guaranteed that mmm can be represent as 2k2^k2k, where kkk is a non-negative integer. Output For each test case, print a line with mmm integers, the iii-th number denotes the number of non-empty subtree of TTT which value are equal to iii. The answer is huge, so please module 109710^971097. Sample Input
2
4 4
2 0 1 3
1 2
1 3
1 4
4 4
0 1 3 1
1 2
1 3
1 4Sample Output
3 3 2 3
2 4 2 3solution 设dp[u][i]dp[u][i]dp[u][i]表示以uuu为根的子树内异或值为jjj的方案数 有一个很暴力的转移 dp[u][i]∑j⊗kidp[u][j]∗dp[v][k]v∈son[u]dp[u][i]\sum_{j\otimes ki}dp[u][j]*dp[v][k]v∈son[u]dp[u][i]j⊗ki∑dp[u][j]∗dp[v][k]v∈son[u] 发现直接可以FWT_xorFWT\_xorFWT_xor直接dfsdfsdfs暴力做就降了一个mmm code
#include cstdio
#include vector
#include cstring
using namespace std;
#define mod 1000000007
#define ll long long
#define MAXN 1050
vector int G[MAXN];
const ll inv ( mod 1 ) 1;
int T, n, m, N;
ll ans[MAXN];
ll dp[MAXN][MAXN];void FWT( ll *w, int opt ) {for( int i 2;i N;i 1 )for( int p i 1, j 0;j N;j i )for( int k j;k j p;k ) {ll x w[k], y w[k p];w[k] ( x y ) % mod;w[k p] ( x - y mod ) % mod;if( opt -1 )w[k] w[k] * inv % mod, w[k p] w[k p] * inv % mod;}
}void dfs( int u, int fa ) {FWT( dp[u], 1 );for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa ) continue;dfs( v, u );for( int j 0;j N;j )dp[u][j] dp[u][j] * dp[v][j] % mod;}FWT( dp[u], -1 );dp[u][0] ( dp[u][0] 1 ) % mod;//一个子树是可以不选的 所以要1FWT( dp[u], 1 );
}int main() {scanf( %d, T );while( T -- ) {scanf( %d %d, n, m );memset( dp, 0, sizeof( dp ) );memset( ans, 0, sizeof( ans ) );for( int i 1;i n;i ) G[i].clear();N m;for( int i 1, x;i n;i )scanf( %d, x ), dp[i][x] ;for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );G[u].push_back( v ), G[v].push_back( u );}dfs( 1, 0 );for( int i 1;i n;i )FWT( dp[i], -1 );for( int i 1;i n;i )dp[i][0] ( dp[i][0] - 1 mod ) % mod;for( int i 1;i n;i )for( int j 0;j m;j )ans[j] ( ans[j] dp[i][j] ) % mod;printf( %lld, ans[0] );for( int i 1;i m;i )printf( %lld, ans[i] ); printf( \n );} return 0;
}
