题面
https://www.luogu.org/problemnew/show/P4517
题解
这道题对我来说意义重大，是我花了很长时间独立完成的dp。
分析题目
给出一个仙人掌，对于一个点集$S$，把原图中使他联通的最小的边集记做$H(S)$，
求$sum_{S subseteq V} |H(S)|$
从考虑边的贡献的思路开始。
对于非环边，假设它把$V$分成了$S$和$T$两个区域，如果它被使用，当且仅当其中存在两个点$a,b$ 使得 $a in S b in T$，统计$S$和$T$集合中元素的个数即可。
对于环边，我们把它放到环中考虑，环上如果有边，则边一定是连续的（若不连续，子图不能联通）
那么对于一个环点的子集，这个连续的边的区间该怎么选？
找到其中最大的空缺，把环的长度去掉空缺的长度，即为答案区间。
所以贡献与最大的空缺有关。
设$f[x][y]$为从起点到$x$点，起点一定选，并且$x$点一定选，最大的空缺长度为$y$ 的集合个数是多少。
显然可以得到 $F[x][y] = (sum_{dis(i,x) le y} F[i][y] + sum_{j<y} F[x-y][j]) imes v[x]$
观察到转移可以写成一个前缀和的形式。
所以我们就可以把$F[x][y]$都算出来了。
考虑怎么统计答案。
设$ans$为所有的$|H(S)|$之和。
本来我的想法是 当$F[x][y]$满足$dis(start,x) le cirlen-y$ 把$F[x][y]$按长度为权加到$ans$里 把环上的每个点作为起点做一次$dp$
发现这样是假的，因为当取到等号时，一个集合可能被算多次。
所有我们考虑怎么统计。
其实解决方法也很简单，当我却想了很久。
今天$gyfan$给我们做的题中，一个很简单的操作我竟然不会实现，写的代码巨烦无比，并且逻辑错误，还说题目出错了，现在看来，是太浮躁了吧，如果让$AYSN$写的话，他肯定很快能想到。
不要把$F[x][y]$看成有向的，直接把他看成集合的集合。
对于每个起点$dp$到一样的终点即可。
这样一定是不重不漏的。
不重：对于起点$x$和$y$的$F$，他们代表的集合中的起点一定是$x$和$y$，如果$x ot=y$，则集合的每个元素的起点都和另一个元素的起点不同，自然不会重复，对于起点相同的$F[x]$和$F[y]$来说，他们的终点不同。综上，对于一个元素，一定不会被重复分到两个不同的集合中。
不漏：对于一个长度（这里的长度指点到点的有向长度）大于$1$（长度为$1$时，对答案无贡献，不考虑），一定有最左边的点和最右边的点，所以一定会出现在$start=s$的$F[t]$中，所以一定不漏。
然后就可以统计答案了。
- 前缀和优化$dp$时，宽不能少算，即使$F[i][j]=0$也要算$sum[i][j]$，并且$sum[0][i]$和$sum[i][0]$也要算。这个地方已经被坑了两次了。
- $tarjan(x)$时，注意判树边时，记得$s.pop()$ （可以理解成，脱下裤子后，发现...，再重新把裤子传上）
- $tarjan(x)$时，对于$pop$出的$t$，暴力找环边，复杂度是真的，因为均摊。
- $tarjan(x)$时，勿忘$low[x]=min(low[x],low[y])$，$low[x]=min(dfn[y],low[x])$不容易忘。。。。
- $tarjan(x)$时，其他细节见上一题。
- 注意取模的减法，要加上$mod$，防止减了之后小于零（虽然这种可能性很小）
#include<cstdio> #include<cstring> #include<iostream> #include<stack> #include<vector> #define INF 1000000007 #define ri register int #define LL long long #define N 205 #define M 500 using namespace std; LL ans=0; int n,m,tot=0,a[M],b[M],vis[N],cir[M],pp[M]; vector<int> c[N]; int v[N],myn; inline int read() { int ret=0,f=0; char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') ret*=10,ret+=ch-'0',ch=getchar(); return f?-ret:ret; } stack<int> s; struct graph { vector<int> to[N],id[N]; int dfn[N],low[N],cnt; void add_edge(int a,int b,int c) { to[a].push_back(b); id[a].push_back(c); to[b].push_back(a); id[b].push_back(c); } void tarjan(int x) { dfn[x]=low[x]=++cnt; s.push(x); for (ri i=0,l=to[x].size();i<l;i++) { int y=to[x][i]; if (dfn[y]) { low[x]=min(low[x],dfn[y]); } else { tarjan(y); low[x]=min(low[x],low[y]); if (low[y]>=dfn[x]) { if (s.top()==y) { s.pop(); continue; } ++tot; int t,pret=x; do { t=s.top(); c[tot].push_back(t); s.pop(); for (ri j=0,l2=id[t].size();j<l2;j++) if (to[t][j]==pret) {cir[id[t][j]]=tot;break;} pret=t; } while (t!=y); c[tot].push_back(x); cir[id[x][i]]=tot; } } } }
void tonji(int x,int ff1,int ff2,int &cnt) { vis[x]=1; ++cnt; for (ri i=0,l=to[x].size();i<l;i++) { int y=to[x][i]; if (y==ff1 || vis[y] || y==ff2) continue; tonji(y,ff1,ff2,cnt); } } } G; LL f[N][N],sumh[N][N],sums[N][N]; LL sh(int x,int y) { if (x>=0) return sumh[x][y]; else return 0; } void dp(int lent,int cur,int start) { memset(f,0,sizeof(f)); memset(sumh,0,sizeof(sumh)); memset(sums,0,sizeof(sums)); sumh[start][0]=sums[start][0]=f[start][0]=(pp[v[c[cur][start]]]-1+INF)%INF; for (ri i=1;i<=lent;i++) sumh[start+i][0]=sumh[start+i-1][0]; for (ri i=1;i<=lent;i++) sums[start][i]=sums[start][i-1]; for (ri l=1;start+l<lent;l++) { for (ri k=1;k<=lent;k++) { f[start+l][k]=((sumh[start+l-1][k]-sh(start+l-k-1,k)+INF+sums[start+l-k][k-1])%INF*1LL*(pp[v[c[cur][(start+l)%lent]]]-1+INF)%INF)%INF; sumh[start+l][k]=(sumh[start+l-1][k]+f[start+l][k])%INF; sums[start+l][k]=(sums[start+l][k-1]+f[start+l][k])%INF; int ml=max(k,lent-l); ans+=(lent-ml)*1LL*f[start+l][k],ans%=INF; } } } LL pow(LL a,int n) { LL ret=1; for (;n;n>>=1,a=(a*a)%INF) if (n&1) ret=(ret*a)%INF; return ret; } int main() { pp[0]=1; for (ri i=1;i<N;i++) pp[i]=(pp[i-1]+pp[i-1])%INF; scanf("%d %d",&n,&m);
for (ri i=1;i<=m;i++) { int u,v; scanf("%d %d",&u,&v); a[i]=u; b[i]=v; G.add_edge(u,v,i); } G.cnt=0; G.tarjan(1); for (ri i=1;i<=m;i++) if (cir[i]==0) { memset(vis,0,sizeof(vis)); int t1=0; G.tonji(a[i],b[i],-1,t1); memset(vis,0,sizeof(vis)); int t2=0; G.tonji(b[i],a[i],-1,t2); ans+=(pp[t1]-1+INF)*1LL*(pp[t2]-1+INF); ans%=INF; } for (ri i=1;i<=tot;i++) { myn=c[i].size(); for (ri j=0;j<myn;j++) c[i].push_back(c[i][j]); for (ri j=1;j<=myn;j++) { memset(vis,0,sizeof(vis)); v[c[i][j]]=0; G.tonji(c[i][j],c[i][j-1],c[i][j+1],v[c[i][j]]); } for (ri j=0;j<myn;j++) dp(myn,i,j); } printf("%lld",ans*1LL*pow(pp[n],INF-2)%INF); return 0; }