P4517 [JSOI2018]防御网络

#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;
}