锐客网

  1. 首页 > it技术 > >

loj|[loj2340][FWT][子集卷积]州区划分

fwtloj

Description

传送门
【loj|[loj2340][FWT][子集卷积]州区划分】题解
看懂题需要一会…
朴素的dp就可以列出一个方程
f [ m a s k ] = 1 r [ i ] p ∑ j ∣ k = m a s k f [ j ] ? r [ k ] p f[mask]=\frac{1}{r[i]^p}\sum_{j|k=mask} f[j]*r[k]^p f[mask]=r[i]p1?j∣k=mask∑?f[j]?r[k]p
其中 r [ i ] r[i] r[i]表示 i i i状态下的人数
那么暴力枚举子集就是 3 n 3^n 3n的噜
然后发现这其实是一个裸的子集卷积
于是就可以直接卷一下完事了…
#include #include #include #include #include #include #include #include #include #include #include #define LL long long #define mp(x,y) make_pair(x,y) #define pll pair #define pii pair using namespace std; inline int read() { int f=1,x=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar(); } return x*f; } int stack[20]; inline void write(int x) { if(x<0){putchar('-'); x=-x; } if(!x){putchar('0'); return; } int top=0; while(x)stack[++top]=x%10,x/=10; while(top)putchar(stack[top--]+'0'); } inline void pr1(int x){write(x); putchar(' '); } inline void pr2(int x){write(x); putchar('\n'); } const int MAXN=22; const int mod=998244353; const int MAXMASK=(1<<21); int A[MAXN],B[MAXN]; void fwt(int *y,int len,int on) { for(int i=1; i>=1; } return ret; } int f[MAXN][MAXMASK],ok[MAXMASK],bin[25],w[MAXN],r[MAXMASK],ct[MAXMASK]; int C[MAXN][MAXMASK],inv[MAXMASK]; int n,m,P,mp[MAXN][MAXN]; int du[MAXN],rt[MAXN]; int findrt(int x){return rt[x]==x?rt[x]:rt[x]=findrt(rt[x]); } void ad(int &x,int y){x+=y; if(x>=mod)x-=mod; } int main() { // freopen("walk2.in","r",stdin); bin[0]=1; for(int i=1; i<=21; i++)bin[i]=bin[i-1]<<1; n=read(); m=read(); P=read(); for(int i=1; i<=m; i++) { int x=read(),y=read(); mp[x][y]++; mp[y][x]++; } for(int i=1; i<=n; i++)w[i]=read(); for(int i=0; i

    推荐阅读


    上一篇：线段树|uoj#57./bzoj3051 【WC2013】平面图 //平面图转对偶图

    下一篇：2015-1-29冬令营日志