模板题

传送门

#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 ll read()
{ll 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 mod 998244353
#define inv2 499122177ll 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]=1ll*a[j+k]*inv2%mod,a[i+j+k]=1ll*a[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;
}

（bzoj 4589）Hard Nim

传送门

题意：n堆石子,每堆石子的数量都是不大于m的质数的Nim游戏，求先手必败的局面数量模1000000007

Solution

• 用线筛求出不大于m的质数
• \(是质数a[i]=[i是质数]\)
• 直接对FWT(a)进行快速幂
• 答案就是a[0]

#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

传送门

题意：给出一棵树，求异或和为[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！