bzoj5315/luoguP4517 [JSOI2018]防御网络(仙人掌,dp)

rikurika 2021-08-07 原文

仙人掌dp的好题，dp方面值得一做。

bzoj5315/luoguP4517 防御网络(仙人掌,dp)

bzoj Luogu

题目描述略(太长了)

题解时间

本题和斯坦纳树无关。

题面保证了是一个仙人掌。。。？

但这个环之间甚至交点都没有。

对于不在环上的边很好弄。

在环上的很难单独考虑。

所以直接考虑一次算出一个环的贡献。

假设我们现在选了一个环上的不止一个点。

那么其中没有被选中的边肯定是连续的一段并且是所有被选中的点分割出的最长的。

这样很容易搞出一个枚举长度 $ l $ 的dp，通过前缀和可以优化到 $ O(n^3) $ 。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long lint;
template<typename TP>inline void read(TP &tar)
{
	TP ret=0,f=1;char ch=getchar();
	while(ch<\'0\'||ch>\'9\'){if(ch==\'-\')ch=-1;ch=getchar();}
	while(ch>=\'0\'&&ch<=\'9\'){ret=ret*10+ch-\'0\';ch=getchar();}
	tar=ret*f;
}
namespace RKK
{
const int N=211,mo=1000000007;
lint fpow(lint a,lint p){lint ret=1;while(p){if(p&1)ret=ret*a%mo;a=a*a%mo,p>>=1;}return ret;}
struct sumireko{int to,ne;}e[N<<2];int he[N],ecnt=1;
void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f],he[f]=ecnt;}
lint b2[N],b1[N];
int n,m;lint ans;
bool lonr[N<<1];
int fa[N],fi[N],sz[N],dep[N];
vector<int> rnd[N];int rcnt;
void getrnd(int x,int anc)
{
	rcnt++;
	for(int px=x;px!=anc;px=fa[px])
		rnd[rcnt].push_back(px),lonr[fi[px]]=1;
	rnd[rcnt].push_back(anc);
}
void dfs(int x)
{
	sz[x]=1;
	for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(t!=fa[x])
	{
		if(!sz[t]) fa[t]=x,dep[t]=dep[x]+1,fi[t]=i>>1,dfs(t),sz[x]+=sz[t];
		else if(dep[t]<dep[x])
		{
			lonr[i>>1]=1;
			getrnd(x,t);
		}
	}
}
int s[N];
lint dp[N],dg[N],ds[N];
void work(int ri)
{
	vector<int> &ve=rnd[ri];
	int len=ve.size();
	for(int i=1;i<len;i++) s[i]=sz[ve[i-1]];s[len]=n;
	for(int i=len;i>1;i--) s[i]-=s[i-1];
	memset(dp+1,0,8*len);
	for(int l=1;l<=len;l++)
	{
		for(int i=1;i<=l;i++)
		{
			memset(dg+1,0,8*len),memset(ds+1,0,8*len);
			dg[i]=ds[i]=b1[s[i]];
			for(int j=i+1;j<=len;j++)
			{
				dg[j]=b1[s[j]]*(ds[j-1]-ds[max(1,j-l)-1]+mo)%mo;
				ds[j]=(ds[j-1]+dg[j])%mo;
			}
			(dp[l]+=ds[len]-ds[max(i+1,len-l+i)-1]+mo)%=mo;
		}
	}
    for(int i=1;i<=len;++i)
        (ans+=(dp[i]-dp[i-1]+mo)*(len-i))%=mo;
}

int Iris()
{
	b2[0]=1;for(int i=1;i<=200;i++) b2[i]=(b2[i-1]<<1)%mo,b1[i]=b2[i]-1;
	read(n),read(m);for(int i=1,x,y;i<=m;i++) read(x),read(y),addline(x,y),addline(y,x);
	dfs(1);
	for(int i=1;i<=m;i++)if(!lonr[i])
		(ans+=b1[min(sz[e[i<<1].to],sz[e[i<<1|1].to])]*b1[n-min(sz[e[i<<1].to],sz[e[i<<1|1].to])]%mo)%=mo;
	for(int i=1;i<=rcnt;i++) work(i);
	(ans*=fpow(b2[n],mo-2))%=mo;
	printf("%lld\n",ans);
	return 0;
}
}
int main(){return RKK::Iris();}