锐客网

  1. 首页 > it技术 > >

DP|【WC2018】州区划分

dpnttFFT题解FWT等线性变换

Description 原题链接
部分分 【DP|【WC2018】州区划分】容易想到 O(3n)O ( 3 n ) 的子集DP
fs=∑t?sft?gs?tf s = ∑ t ? s f t ? g s ? t
做完了 fsf s 之后还要让 fs=fs?invsf s = f s ? i n v s
100% 发现上面那个方程就是一个子集卷积，只不过会自己卷自己的。
回顾子集卷积怎么搞，类似的，设 f[i][s]f [ i ] [ s ]
我们从小到大枚举这个 ii ，相当于分层进行转移。
同理分层FMT就可以了，复杂度是一样的，于是可以 O(2nn2)O ( 2 n n 2 ) 解决。
Codes

#include #include #include #define fo(i,a,b) for(int i=a; i<=b; ++i) #define fd(i,b,a) for(int i=b; i>=a; --i) #define efo(i,v,u) for(int i=BB[v],u=B[BB[v]][1]; i; i=B[i][0],u=B[i][1]) #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)<(y)?(x):(y)) #define mset(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; char ch; int read(){int n=0,p=1; for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar())if(ch=='-') p=-1; for(; '0'<=ch && ch<='9'; ch=getchar()) n=n*10+ch-'0'; return n*p; } const int N=23,M=(1<<21)+5,mo=998244353; ll qmi(ll x,ll n) { ll t=1; for(; n; n>>=1,x=x*x%mo) if(n&1) t=t*x%mo; return t; } bool map[N][N]; int _2[N],n,m,p,in[N],bitcnt[M],fa[N]; int getfa(int x){return fa[x]?fa[x]=getfa(fa[x]):x; } ll w[N],sum[M],pd[M],f[N][M],g[N][M]; void fmt(ll *a,int sig=1) { fo(i,1,n) fo(s,0,_2[n]-1) if(s&_2[i-1]) a[s]=(a[s]+(sig>0?(a[s^_2[i-1]]):(mo-a[s^_2[i-1]])))%mo; } int main() { int x,y; n=read(),m=read(),p=read(); _2[0]=1; fo(i,1,n) _2[i]=_2[i-1]<<1; fo(i,1,m) { x=read(),y=read(); map[x][y]=map[y][x]=1; } fo(i,1,n) w[i]=read(); fo(s,1,_2[n]-1) { fo(i,1,n) if(s&_2[i-1]) sum[s]=(sum[s]+w[i])%mo,++bitcnt[s]; pd[s]=sum[s]=qmi(sum[s],p); sum[s]=qmi(sum[s],mo-2); if(bitcnt[s]==1) {pd[s]=0; continue; } mset(fa,0); mset(in,0); bool ok=0; fo(i,1,n) if(s&_2[i-1]) { fo(j,1,n) if(s&_2[j-1]) if(map[i][j]) { ++in[i]; int fi=getfa(i),fj=getfa(j); if(fi!=fj) fa[fj]=fi; } if(in[i]&1) {ok=1; break; } if(!in[i]) {ok=1; break; } } int cnt=0; fo(i,1,n) if(s&_2[i-1]) if(i==getfa(i)) ++cnt; if(cnt>1) continue; if(!ok) pd[s]=0; } fo(s,1,_2[n]-1) g[bitcnt[s]][s]=pd[s]; fo(i,0,n) fmt(g[i]); f[0][0]=1; fo(k,1,n) { fmt(f[k-1]); fo(i,0,k) fo(s,0,_2[n]-1) f[k][s]=(f[k][s]+f[i][s]*g[k-i][s])%mo; fmt(f[k],-1); fo(s,0,_2[n]-1) f[k][s]=f[k][s]*sum[s]%mo; } printf("%lld\n",f[n][_2[n]-1]); return 0; }

    推荐阅读


    上一篇：STM32之RCC配置

    下一篇：LOJ#2340.|LOJ#2340. 「WC2018」州区划分