模板题
## [ 传送门 ](https://www.luogu.org/problemnew/show/P4717)
```
#include
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&chdefine mod 998244353
define inv2 499122177
ll a[1<<17],b[1<<17],c[1<<17],N;
inline void FWT_or(ll a,int f)
{
register int i,j,p,k;
for(i=1;i<N;i<<=1)for(p=i<<1,j=0;j<N;j+=p)for(k=0;k<i;++k)
a[i+j+k]=(a[i+j+k]+a[j+k]f+mod)%mod;
}
inline void FWT_and(ll a,int f)
{
register int i,j,p,k;
for(i=1;i<N;i<<=1)for(p=i<<1,j=0;j<N;j+=p)for(k=0;k<i;++k)
a[j+k]=(a[j+k]+a[i+j+k]f+mod)%mod;
}
inline void FWT_xor(ll a,bool f)
{
register int i,j,p,k;
for(i=1;i<N;i<<=1)for(p=i<<1,j=0;j<N;j+=p)for(k=0;k<i;++k)
{
int X=a[j+k],Y=a[i+j+k];
a[j+k]=(X+Y)%mod;a[i+j+k]=(X+mod-Y)%mod;
if(f==0)a[j+k]=1lla[j+k]inv2%mod,a[i+j+k]=1lla[i+j+k]*inv2%mod;
}
}
int main()
{
N=1<<read();register int i;
for(i=0;i<N;++i) a[i]=1ll*read()%mod;
for(i=0;i<N;++i) b[i]=1ll*read()%mod;
FWT_or(a,1);FWT_or(b,1);
for(i=0;i<N;++i) c[i]=1ll*a[i]*b[i]%mod;
FWT_or(a,-1);FWT_or(b,-1);FWT_or(c,-1);
for(i=0;i<N;++i) printf("%lld ",c[i]);puts("");
FWT_and(a,1);FWT_and(b,1);
for(i=0;i<N;++i) c[i]=1ll*a[i]*b[i]%mod;
FWT_and(a,-1);FWT_and(b,-1);FWT_and(c,-1);
for(i=0;i<N;++i) printf("%lld ",c[i]);puts("");
FWT_xor(a,1);FWT_xor(b,1);
for(i=0;i<N;++i) c[i]=1ll*a[i]*b[i]%mod;
FWT_xor(a,0);FWT_xor(b,0);FWT_xor(c,0);
for(i=0;i<N;++i) printf("%lld ",c[i]);puts("");
return 0;
}
<br/>
<br/>
## （bzoj 4589）Hard Nim
<br/>
## [<font color=purple> 传送门 </font>](https://www.lydsy.com/JudgeOnline/problem.php?id=4589)
题意：n堆石子,每堆石子的数量都是不大于m的质数的Nim游戏，求先手必败的局面数量模1000000007
<br/>
## <font color=DarkSlateBlue style="font-weight:bold">Solution </font>
> - 用线筛求出不大于m的质数
> - $是质数a[i]=[i是质数]$
> - 直接对FWT(a)进行快速幂
> - 答案就是a[0]
<br/><br/>
```c++
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define MN 65540
int prime[MN],tot;
bool mark[MN];
#define mod 1000000007
int a[MN],inv2,N;
inline int fpow(int x,int m)
{
int res=1;
while(m)
{
if(m&1) res=(int)(1ll*res*x%mod);
x=(int)(1ll*x*x%mod);m>>=1;
}
return res;
}
inline void init()
{
inv2=fpow(2,mod-2);
mark[1]=1;register int i,j;
for(i=2;i<=MN-5;i++)
{
if(!mark[i]){prime[++tot]=i;}
for(j=1;j<=tot&&prime[j]*i<=MN-5;++j)
{
mark[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
inline void FWT_xor(int *a,bool f)
{
register int i,j,p,k;
for(i=1;i<N;i<<=1)for(p=i<<1,j=0;j<N;j+=p)for(k=0;k<i;++k)
{
int X=a[j+k],Y=a[i+j+k];
a[j+k]=(X+Y)%mod;a[i+j+k]=(X+mod-Y)%mod;
if(f==0)a[j+k]=1ll*a[j+k]*inv2%mod,a[i+j+k]=1ll*a[i+j+k]*inv2%mod;
}
}
int main()
{
register int n,m,i,j;
init();
while(~scanf("%d%d",&n,&m))
{
for(N=1;N<=m;N<<=1);
memset(a,0,sizeof a);
for(i=1;i<=m;++i) a[i]=(!mark[i]);
FWT_xor(a,1);
for(i=0;i<N;++i) a[i]=fpow(a[i],n);
FWT_xor(a,0);
printf("%d\n",a[0]);
}
return 0;
}
（hdu 5909）Tree Cutting
## [ 传送门 ](http://acm.hdu.edu.cn/showproblem.php?pid=5909)
题意：给出一棵树，求异或和为[0, m-1]的非空连通子图的个数
Solution
树形dp
f[i][j]表示以i为根的子树内，异或和为j的联通块个数
用FWT优化转移
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(a,b) (a^=b^=a^=b)
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
#define MN 2005
#define mod 1000000007
#define inv2 500000004
int val[MN],en,hr[MN];
struct edge{int to,nex;}e[MN<<1];
int N,f[MN][1<<11],tmp[1<<11],ans[1<<11];
inline void ins(int f,int t)
{
e[++en]=(edge){t,hr[f]};hr[f]=en;
e[++en]=(edge){f,hr[t]};hr[t]=en;
}
inline void FWT_xor(int *a,bool f)
{
register int i,j,p,k;
for(i=1;i<N;i<<=1)for(p=i<<1,j=0;j<N;j+=p)for(k=0;k<i;++k)
{
int X=a[j+k],Y=a[j+i+k];
a[j+k]=(X+Y)%mod,a[j+i+k]=(X+mod-Y)%mod;
if(f==0) a[j+k]=1ll*a[j+k]*inv2%mod,a[j+i+k]=1ll*a[j+i+k]*inv2%mod;
}
}
inline void rw(int *a,int *b)
{
FWT_xor(a,1);FWT_xor(b,1);register int i;
for(i=0;i<N;++i) a[i]=1ll*a[i]*b[i]%mod;
FWT_xor(a,0);
}
inline void dfs(int x,int fa)
{
f[x][val[x]]=1;
register int i,j;
for(i=hr[x];i;i=e[i].nex)if(e[i].to^fa)
{
dfs(e[i].to,x);
for(j=0;j<N;++j) tmp[j]=f[x][j];
rw(f[x],f[e[i].to]);
for(j=0;j<N;++j) (f[x][j]+=tmp[j])%=mod;
}
for(i=0;i<N;++i) (ans[i]+=f[x][i])%=mod;
}
int main()
{
register int Case=read(),n,m,i;
while(Case--)
{
n=read(),m=read();N=m;
// for(N=1;N<=m;N<<=1);
en=0;
memset(hr,0,sizeof hr);
memset(ans,0,sizeof ans);
memset(f,0,sizeof f);
for(i=1;i<=n;++i) val[i]=read();
for(i=1;i<n;++i) ins(read(),read());
dfs(1,0);
for(i=0;i<m-1;i++) printf("%lld ",ans[i]);
printf("%lld\n",ans[m-1]);
}
return 0;
}
（bzoj 4036）[HAOI2015]按位或
传送门
Description
刚开始你有一个数字0，每一秒钟你会随机选择一个[0,2^n-1]的数字，与你手上的数字进行或（c++,c的|,pascal的or）操作。
选择数字i的概率是p[i]。保证0<=p[i]<=1，Σp[i]=1问期望多少秒后，你手上的数字变成2^n-1。
Solution
相当于给你一个集合求最后一个元素出现的时间
可以用\(minmax\) 容斥一波，这样就是求每个子集中第一个元素出现的时间\(min(T)\)啦
我们设\(P(T)\)表示取到\(T\)的子集的概率
\[P(min(T)==k)=P(S-T)^{k-1}(1-P(S-T))
\]然后因为：
\[若P(x==k)=(1-p)^{k-1}p(k \in N^{+})，则E(x)=\frac{1}{p}
\]所以：
\[E(min(T))=\frac{1}{1-P(S-T)}
\]问题在于，如何求\(P(T)\)呢
显然
\[P(T)=\sum_{x⊆T}p(x)，这里我们把一个数都当作一个集合，p(x)就是题目给出的得到x的概率
\]求子集和？可以用像「PKUWC2018」随机游走 一样的子集和dp，当然，也可以直接\(FWT\)变换一下。
Code
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n,N,num[1<<20];
double P[1<<20],Ans=0.;
int main()
{
scanf("%d",&n);N=1<<n;
register int i,j,p,k;
for(i=0;i<N;++i)scanf("%lf",&P[i]);
for(i=1;i<N;i<<=1)for(p=i<<1,j=0;j<N;j+=p)for(k=0;k<i;++k) P[i+j+k]+=P[j+k];
for(i=1;i<N;++i)
{
num[i]=num[i>>1]+(i&1);
if(1-P[(N-1)^i]<1e-9) return 0*puts("INF");
Ans+=((num[i]&1)?1.:-1.)*(1./(1.-P[(N-1)^i]));
}
printf("%.9lf\n",Ans);
return 0;
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！
![[OpenCV-Python] 14 几何变换](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)