专栏文章

题解：P10140 [USACO24JAN] Island Vacation P

ttobie
P10140题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7vb5z
此快照首次捕获于
2025/12/04 00:23
3 个月前
此快照最后确认于
2025/12/04 00:23
3 个月前
查看原文
考虑拆分一次游走过程：我们定义“一次操作”为在 uu 处进行一次判定后发现没有结束，然后从 uu 走到 vv。
设当前状态下 uu 的出度为 dd，则该次操作的贡献为 (1−pu)d\dfrac {(1-p_u)} d。
以下 dp 过程中使用“概率”一词似乎并不是非常恰当，我们认为一条路径的“权值”为每次操作的贡献的乘积。自然想到设 fuf_u 表示所有第一次走到 uu 的路径的权值和。
首先建出圆方树。对于一个节点 uu，如果我们钦定最后在 uu 节点停下，则我们的过程必然会分为如下阶段：
  1. 首先我们要走到 uu，贡献为 fuf_u。
  2. 然后我们可能会穿过 uu 节点子树内的若干个环回到 uu 节点，然后再下一次操作的“判定”时倒闭。
这里我们发现从 uu 出发穿过一个环然后回到 uu 的过程也是很重要的。结合以上分析，我们定义如下状态：
  1. fuf_u 表示从 11 出发，第一次走到 uu 的所有路径权值和。
  2. gug_u 表示从 faufa_u 出发，绕着 uu 对应的点走一圈的路径权值和。gug_u 只在方点处有定义。
  3. huh_u 表示从 11 出发到达 uu 后，在 uu 上绕若干圈之后，再从 uu 出发走一步的路径在 uu 之后的所有操作的权值和。
gug_u 的转移是最容易的：蓝色环的贡献为 hvh_v，红色边的贡献直接计算即可。
现在考虑计算 huh_u。
假设我们从 uu 节点出发，选择了 SS 中的方点对应的环，最后回到 uu 节点的贡献差不多长成这个样子：
d0∣S∣d0!!∣S∣!(d0−2∣S∣)!!∏v∈Sgv\frac {d_0^{|S|} d_0!!|S|!}{(d_0-2|S|)!!}\prod_{v\in S} g_v
解释一下意思：每个环的贡献显然就是 gvg_v，先乘上，然后考虑修正。
每次从 uu 出发时，uu 的出度分别为 d0,d0−2,d0−4,⋯d_0,d_0-2,d_0-4,\cdots，而 gvg_v 里的贡献为 1d\frac 1 d，所以需要乘上 dd0−2k\frac d {d_0-2k} 的修正项；SS 中元素没有顺序还会带来 ∣S∣!|S|! 的贡献；
你发现我们只在乎选取的集合的 ∣S∣|S| 和 ∏gv\prod g_v，跑一遍背包，然后带入公式计算即可。
写代码时发现这个式子还需要进行一些修补，比如需要考虑走完之后的那个红色的出边，以及 u=1u=1 时的 d0d_0 和其他情况略有不同，需要特别注意。
计算 gug_u 和 huh_u 可以自底向上跑一遍 dfs。复杂度 O(n2)O(n^2)。
接下来考虑如何计算 fuf_u。
如图。目前已知你第一次走到了 uu，则你会先走绿色的环，然后颜色红色边走到 vv，途中还可能经过一些蓝色的环。
蓝色的环贡献就是 hxh_x，红色边可以直接计算，现在只需要考虑绿色边。
我们发现，可以选的绿色圈的集合 S0S_0 是 uu 子树内所有可以选择的圈的集合 SS 去掉当前这个环，所以跑一个撤销背包即可，式子同上。
至于答案的计算，你只需要把 fuf_u 和 huh_u 拼起来就行了。
综上，总复杂度为 O(n2)O(n^2)，瓶颈在背包。可以用分治 NTT 做到 O(nlog⁡2n)O(n \log ^2 n)，懒得写了，就这样吧。
CPP
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N=20009;
const int mod=1e9+7;

int inv[N];

int n,ncnt=0,a[N],deg[N];

vector<int> to[N];
int siz[N];

namespace Build{

vector<int> G[N];
int m;

int dfn[N],low[N],dfncnt=0;
int sta[N],tp=0;

void dfs(int u,int f)
{
	dfn[u]=low[u]=++dfncnt;
	sta[++tp]=u;
	for(int v:G[u])
	if(!dfn[v])
	{
		dfs(v,u);
		low[u]=min(low[u],low[v]);
		if(low[v]==dfn[u])
		{
			ncnt++;
			to[ncnt].push_back(u);
			to[u].push_back(ncnt);
			siz[ncnt]=1;
			for(int x=0;x!=v;tp--)
			{
				x=sta[tp];
				to[ncnt].push_back(x);
				to[x].push_back(ncnt);
				siz[ncnt]++;
			}
		}
	}
	else low[u]=min(low[u],dfn[v]);
}

void ReadIn()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n*2;i++) to[i].clear(),G[i].clear(),siz[i]=0;
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		G[u].push_back(v),G[v].push_back(u);
	}
	for(int i=1;i<=n*2;i++) dfn[i]=low[i]=0;
	dfncnt=0,tp=0;
	for(int i=1;i<=n;i++) deg[i]=G[i].size();
	ncnt=n;
	dfs(1,0);
}

}
using Build::ReadIn;

int g[N],h[N];

void dfs1(int u,int f)
{
	if(u>n)
	{
		g[u]=2ll*(mod+1-a[f])*inv[deg[f]]%mod;
		for(int v:to[u])
		if(v!=f)
		{
			dfs1(v,u);
			g[u]=1ll*g[u]*h[v]%mod;
		}
	}
	else
	{
		for(int v:to[u]) if(v!=f) dfs1(v,u);
		vector<int> tmp; tmp.push_back(1);
		for(int v:to[u])
		if(v!=f&&siz[v]>2)
		{
			tmp.push_back(0);
			for(int i=(int)(tmp.size())-1;i;i--)
			tmp[i]=(1ll*tmp[i-1]*g[v]+tmp[i])%mod;
		}
		int d1=deg[u],d2=deg[u]-(f!=0),s1=(mod+1-a[u])%mod;
		for(int i=0;i<tmp.size();i++)
		{
			h[u]=(h[u]+1ll*tmp[i]*s1%mod*inv[d2])%mod;
			s1=1ll*s1*d1%mod*inv[d2]%mod*(i+1)%mod;
			d2-=2;
		}
	}
}

int f[N],ans[N];
void dfs2(int u,int fa)
{
	vector<int> tmp; tmp.push_back(1);
	for(int v:to[u])
	if(v!=fa&&siz[v]>2)
	{
		tmp.push_back(0);
		for(int i=(int)(tmp.size())-1;i;i--)
		tmp[i]=(1ll*tmp[i-1]*g[v]+tmp[i])%mod;
	}
	int d1=deg[u], d2=deg[u]-(fa!=0), s1=1;
	for(int i=0;i<tmp.size();i++)
	{
		ans[u]=(ans[u]+1ll*tmp[i]*(d2==0?1:a[u])%mod*s1)%mod;
		s1=1ll*s1*d1%mod*inv[d2]%mod*(i+1)%mod;
		d2-=2;
	}
	ans[u]=1ll*ans[u]*f[u]%mod;
	
	for(int vv:to[u])
	if(vv==fa) continue;
	else if(siz[vv]==2)
	{
		for(int v:to[vv])
		if(v!=u)
		{
			d1=deg[u], d2=deg[u]-(fa!=0), s1=1ll*f[u]*(mod+1-a[u])%mod;
			for(int i=0;i<tmp.size();i++)
			{
				f[v]=(f[v]+1ll*tmp[i]*s1%mod*inv[d2])%mod;
				s1=1ll*s1*d1%mod*inv[d2]%mod*(i+1)%mod;
				d2-=2;
			}
			dfs2(v,vv);
		}
	}
	else
	{
		vector<int> tmp2=tmp;
		for(int i=1;i<tmp.size();i++)
		tmp[i]=(tmp[i]+1ll*(mod-g[vv])*tmp[i-1])%mod;
		tmp.pop_back();
		int coaf=1ll*f[u]*(mod+1-a[u])%mod;
		for(int i=1;i<to[vv].size();i++)
		{
			d1=deg[u], d2=deg[u]-(fa!=0), s1=coaf;
			for(int j=0;j<tmp.size();j++)
			{
				(f[to[vv][i]]+=1ll*tmp[j]*s1%mod*inv[d2]%mod)%=mod;
				s1=1ll*s1*d1%mod*inv[d2]%mod*(j+1)%mod;
				d2-=2;
			}
			coaf=1ll*coaf*h[to[vv][i]]%mod;
		}
		coaf=1ll*f[u]*(mod+1-a[u])%mod;
		for(int i=(int)(to[vv].size())-1;i>=1;i--)
		{
			d1=deg[u], d2=deg[u]-(fa!=0), s1=coaf;
			for(int j=0;j<tmp.size();j++)
			{
				(f[to[vv][i]]+=1ll*tmp[j]*s1%mod*inv[d2]%mod)%=mod;
				s1=1ll*s1*d1%mod*inv[d2]%mod*(j+1)%mod;
				d2-=2;
			}
			coaf=1ll*coaf*h[to[vv][i]]%mod;
		}
		
		swap(tmp,tmp2);
		
		for(int v:to[vv]) if(v!=u) dfs2(v,vv);
	}
}

void work()
{
	ReadIn();
	for(int i=1;i<=ncnt;i++) f[i]=g[i]=h[i]=ans[i]=0;
	dfs1(1,0);
	f[1]=1;
	dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	puts("");
}
signed main()
{
	int T;
	scanf("%d",&T);
	inv[0]=inv[1]=1; 
	for(int i=2;i<=20000;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	while(T--) work();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...