「300iq Contest 2」[LOJ 6719] 数仙人掌 Counting Cactus
LOJ上的 $n\leq 18$
如果把仙人掌上的树边看做二元环，那么可以认为仙人掌就是由很多环嵌套在一起的结构
$n\leq 13$
状压$dp$，300iq的题解里给出了状态，但是也只告诉了你状态。。。
令$f(i,S)$为$i$号节点为根，子树集合为$S$的方案数
令$g(i,S)$为$i$号节点为根，子树集合为$S$的方案数，并且强制根上只接了一个环
令$dp(u,v,S)$为钦定一个当前环的开头为$u$，环尾扩展到了$v$，当前包含$S$的方案数
由此得到转移为
1.$f(i,S)\cdot g(j,T)(S\cap T=\empty)\rightarrow f(i,S\cup T)$
2.$dp(u,v,S)\cdot f(d,T)(S\cap T=\empty,(u,v)\in E) \rightarrow dp(u,d,S\cup T)$
3.$dp(u,v,S) ((u,v)\in E)\rightarrow g(u,S)$
实际上涉及到很多计算重复，因此需要在转移过程中加入一些调整:
1.在转移环时，钦定的环开头节点下方不应该接有任何其他节点
2.转移1中$S,T$合并上来时，可以保证$S<T$来避免集合加入顺序的重复
3.当环长>2时，同一个环，同一个开始位置会由于环遍历顺序的不同被转移两次
对于这个问题我的解决方法是: 让$\frac{dp(u,v,S)} {2}\rightarrow g(u,S)$，然后把环长为2的部分加上去
转移过程中涉及到集合运算都是枚举子集，因此复杂度一个很松的上限为$O(n^33^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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
char IO;
int rd(){
int s=0; int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=13,M=1<<N|3,P=998244353;
int n,m;
int G[N];
int f[M][N],g[M][N];
int dp[M][N][N];
int main(){
n=rd(),m=rd();
if(n==1) return puts("1"),0;
rep(i,1,m) {
int u=rd()-1,v=rd()-1;
G[u]|=1<<v,G[v]|=1<<u;
}
int A=(1<<n)-1;
rep(i,0,n-1) g[1<<i][i]=1,dp[1<<i][i][i]=1;
rep(S,1,A) {
rep(u,0,n-1) rep(v,0,n-1) if(S&(1<<u) && S&(1<<v)) {
int R=S^(1<<u);
if(u!=v) R^=(1<<v);
for(int T=R&(R-1);;T=(T-1)&R){
int X=T|(1<<u)|(1<<v),Y=S^X;
if(dp[X][u][v]) rep(d,0,n-1) if(f[Y][d] && G[v]&(1<<d))
dp[S][u][d]=(dp[S][u][d]+1ll*dp[X][u][v]*f[Y][d])%P;
if(!T) break;
}
}
rep(u,0,n-1) rep(v,0,n-1) if(dp[S][u][v] && G[u]&(1<<v))
g[S][u]=(g[S][u]+1ll*(P+1)/2*dp[S][u][v])%P;
rep(i,0,n-1) rep(j,0,n-1) if(i!=j && S&(1<<i) && S&(1<<j) && G[i]&(1<<j))
g[S][i]=(g[S][i]+1ll*(P+1)/2*f[S^(1<<i)][j])%P;
rep(i,0,n-1) f[S][i]+=g[S][i],Mod1(f[S][i]);
rep(i,0,n-1) if(S&(1<<i)) {
int R=S^(1<<i);
for(int T=R&(R-1);T;T=(T-1)&R) {
int X=T,Y=T^R;
if(X>Y) continue;
f[S][i]=(f[S][i]+1ll*f[X|(1<<i)][i]*g[Y|(1<<i)][i])%P;
}
}
}
printf("%d\n",f[A][0]);
}
|
$n\leq 18$
前置知识：集合幂级数的$\ln ,\exp$
同样上面的，一颗仙人掌可以看做若干$\ge 2$环，两两之间在某一个节点上相接构成
不妨先求出环的集合幂级数，枚举环上编号最小的点，然后走环，复杂度为$O(n^32^n)$，常数较小
接下来当然想到枚举环的交点$i$，将当前所有包含$i$的项取出，去掉$i$后求出$\exp$，然后放回去，就能计算相交在$i$上的方案
两部分复杂度均为$O(n^32^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
49
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
enum{N=20,M=1<<18|10,P=998244353};
struct U{
int x;
U(){ } U(int x):x(x){ }
inline void operator += (const U &t){ x+=t.x,x>=P&&(x-=P); }
inline void operator -= (const U &t){ x-=t.x,x<0&&(x+=P); }
inline U operator * (const U &t){ return U(static_cast<unsigned long long>(x)*t.x%P); }
}I[N],F[M][N],H[M][N];
int n,m,G[N],C[M],B[M];
void FWT(int f) {
for(int i=1;i<m;i<<=1) {
for(int l=0;l<m;l+=i*2) {
for(int j=l;j<l+i;++j) {
if(f==1) rep(d,1,n) F[j+i][d]+=F[j][d];
else rep(d,1,n) F[j+i][d]-=F[j][d];
}
}
}
}
void Exp(U *a){
static U b[N];
rep(i,0,n-1) b[i]=a[i+1]*(i+1);
rep(i,0,n-1) {
U t=b[i];
rep(j,1,i) t+=a[j]*b[i-j];
a[i+1]=t*I[i+1];
}
}
int main(){
scanf("%d%d",&n,&m);
if(n==1) return puts("1"),0;
for(int x,y;m--;) scanf("%d%d",&x,&y),x--,y--,G[x]|=1<<y,G[y]|=1<<x;
I[0]=I[1]=1,m=1<<n;
rep(i,0,n-1) B[1<<i]=i;
rep(i,2,n) I[i]=U(P-P/i)*I[P%i];
rep(i,1,m-1) C[i]=C[i&(i-1)]+1;
rep(st,0,n-1) {
H[1<<st][st]=1;
rep(S,0,m-1) rep(i,st,n-1) if(H[S][i].x) {
for(int T=G[i]&~S;T;T&=T-1)
H[S|(T&-T)][B[T&-T]]+=H[S][i];
if(G[i]&(1<<st)) F[S][C[S]]+=H[S][i]*I[1+(C[S]>2)];
H[S][i]=0;
}
}
FWT(1);
for(int i=1;i<m;i<<=1){
for(int l=0;l<m;l+=i*2) for(int j=l;j<l+i;++j) {
rep(k,1,n) F[j+i][k]-=F[j][k];
Exp(F[j+i]+1);
rep(k,1,n) F[j+i][k]+=F[j][k];
}
}
FWT(-1),printf("%d\n",F[m-1][n].x);
}
|
