网站建设源码修改,兼职网站项目建设报告,莱芜网站制作,厦门电子网站建设FWT学习笔记 参考#xff1a; 快速沃尔什变换(FWT)学习笔记FWT 详解 知识点定义#xff1a; 快速沃尔什变换(FWT)主要解决位运算卷积的问题。给定两个数组 \(A\) 和 \(B\) (长度为2的整数幂)#xff1a;\[C_k \sum_{i \oplus jk}A_iB_i\] 其中\(\oplus\)可以是与#xff0… FWT学习笔记 参考 快速沃尔什变换(FWT)学习笔记FWT 详解 知识点定义 快速沃尔什变换(FWT)主要解决位运算卷积的问题。给定两个数组 \(A\) 和 \(B\) (长度为2的整数幂)\[C_k \sum_{i \oplus jk}A_i·B_i\] 其中\(\oplus\)可以是与或异或。FWT利用类似于FFT的想法把 \(A\) 和 \(B\) 分别正变换在一个好的复杂度得到 \(A\) 与 \(B\) 按位卷积的的正变换最后再逆变换回来就是答案。 模版[Luogu4717] #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
typedef long long ll;
const int mod 998244353;
const int inv2 499122177;
const int N (117);
inline int read() {char cgetchar(); int x0,f1;while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
inline void write(int x) {if(x10)write(x/10);putchar(0x%10);
}
using namespace std;
inline int add(int x,int y) {xy;if(xmod)x-mod;return x;
}
inline int sub(int x,int y) {x-y;if(x0)xmod;return x;
}
void FWT_or(int a[],int n,int on) {for(int i1;in;i1) {for(int j0;jn;j(i1)) {for(int k0;ki;k) {int ua[jk], ta[jki];a[jk]u;if(on1)a[jki]add(t,u);else a[jki]sub(t,u);}}}
}
void FWT_and(int a[],int n,int on) {for(int i1;in;i1) {for(int j0;jn;j(i1)) {for(int k0;ki;k) {int u a[jk], ta[jki];if(on1) a[jk]add(u,t);else a[jk]sub(u,t);a[jki]t;}}}
}
void FWT_xor(int a[],int n,int on) {for(int i1;in;i1) {for(int j0;jn;j(i1)) {for(int k0;ki;k) {int ua[jk], ta[jki];a[jk]add(u,t); a[jki]sub(u,t);if(on-1) {a[jk](ll)a[jk]*inv2%mod;a[jki](ll)a[jki]*inv2%mod;}}}}
}
int a[N],b[N],c[N],d[N];
int main() {int n read(), m (1n);rep(i,0,m-1) a[i]read();rep(i,0,m-1) b[i]read();memcpy(c,a,sizeof(c));memcpy(d,b,sizeof(b));FWT_or(c,m,1); FWT_or(d,m,1);rep(i,0,m-1) c[i](ll)c[i]*d[i]%mod;FWT_or(c,m,-1);rep(i,0,m-1)write(c[i]),putchar( );putchar(\n);memcpy(c,a,sizeof(c));memcpy(d,b,sizeof(b));FWT_and(c,m,1); FWT_and(d,m,1);rep(i,0,m-1) c[i](ll)c[i]*d[i]%mod;FWT_and(c,m,-1);rep(i,0,m-1)write(c[i]),putchar( );putchar(\n);memcpy(c,a,sizeof(c));memcpy(d,b,sizeof(b));FWT_xor(c,m,1); FWT_xor(d,m,1);rep(i,0,m-1) c[i](ll)c[i]*d[i]%mod;FWT_xor(c,m,-1);rep(i,0,m-1)write(c[i]),putchar( );putchar(\n);return 0;
}BZOJ4589[Hard Nim] 题意求长度为n元素为小于m的质数且异或和为0的方案数 做法设 \(f[i][j]\) 表示长度为i的序列异或和为j的方案数则\(f[i][x \oplus y] f[i-1][x]·f[1][y]\) 将\(f[1]\)内编号为素数的位置为1其余为0那么\(f[i][k] \sum _{x \oplus yk} f[i-1][x]·f[1][y]\)答案就是要求 \(f[1]\) 卷积 \(n\) 次的f[n][0]又因为每次乘的都是 \(f[1]\) 所以可以先对 \(f[1]\) 求FWT正变换分别n次幂后再加起来最后逆变换出答案向量 \(f[n]\) #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 655371;
const ll mod 1e9 7;
using namespace std;
int m, p[N], notp[N];
ll n,a[N],inv2;
ll q_pow(ll a,ll b) {ll ans 1;while(b) {if(b1) ans(ans*a)%mod;a(a*a)%mod;b1;}return ans;
}
inline ll add(ll x,ll y) {xy;if(xmod)x-mod;return x;
}
inline ll sub(ll x,ll y) {x-y;if(x0)xmod;return x;
}
void FWT_xor(ll a[],int n,int on) {for(int i1;in;i1) {for(int j0;jn;j(i1)) {for(int k0;ki;k) {ll u a[jk], t a[jki];a[jk]add(u,t); a[jki]sub(u,t);if(on-1) {a[jk]a[jk]*inv2%mod;a[jki]a[jki]*inv2%mod;}}}}
}
void init() {inv2 q_pow(2,mod-2);notp[1] 1;for(int i2;i5e4;i) {if(!notp[i])p[p[0]]i;for(int j1;jp[0]p[j]*i5e4;j) {notp[p[j]*i] 1;if(i%p[j]0)break;}}
}
int main() {init();while(~scanf(%lld%d,n,m)) {memset(a,0,sizeof(a));rep(i,1,m) a[i] (!notp[i]);int len;for(len1;lenm;len1);FWT_xor(a,len,1);rep(i,0,len-1) a[i]q_pow(a[i],n);FWT_xor(a,len,-1);printf(%lld\n,a[0]%mod);}return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9478045.html
