【多校2018#3】HDU6321 Problem C. Dynamic Graph Matching

题面在这里

一看就是状压DP了……

\(f_{i,s}\)表示前i个操作,状态为s的方案数

加边操作:\(f_{i,s}=f_{i-1,s-u-v}\)\((u,v)\)是新加的边

然后i这一维可以省略,\(f_s+=f_{s-u-v}\)

删边操作:发现加边的顺序与答案无关,令上一次加边刚好是这次删的边

就变成了撤销上次的操作,\(f_s-=f_{s-u-v}\)

写得好是\(O(Tm\cdot 2^n)\)丝毫不虚

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
#define cl(x,y) memset(x,y,sizeof(x))
inline char nc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
int res=0,f=1;char ch=nc();
while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
return res*f;
}
inline char fstchar(){
char ch=nc();while (ch!='+'&&ch!='-') ch=nc();
return ch;
}

const int maxs=1030,MOD=1e9+7;
int tst,n,q,f[maxs],h[maxs],num1[maxs];
int main(){
tst=red();
for (int s=0;s<1024;s++){
for (int x=s;x;x>>=1) num1[s]+=x&1;
}
while (tst--){
n=red(),q=red(); cl(f,0);f[0]=1;
while (q--){
if (fstchar()=='+'){
int u=red(),v=red();
for (int s=(1<<n)-1;s>=0;s--)
if ((s&(1<<u-1))&&(s&(1<<v-1))) (f[s]+=f[s^(1<<u-1)^(1<<v-1)])%=MOD;
}else{
int u=red(),v=red();
for (int s=0;s<(1<<n);s++)
if ((s&(1<<u-1))&&(s&(1<<v-1))) (f[s]-=f[s^(1<<u-1)^(1<<v-1)])%=MOD;
}
cl(h,0);
for (int s=0;s<(1<<n);s++)
(h[num1[s]]+=f[s])%=MOD;
bool fir=1;
for (int k=1;k<=n/2;k++)
printf(fir?(fir=0,"%d"):" %d",(h[k*2]+MOD)%MOD);
putchar('\n');
}
}
return 0;
}