题解：P13004 [GCJ 2022 Finals] Schrödinger and Pavlov

题意

有

n

个盒子，每个盒子都有一个状态

s[i]

：

C：有一只猫。
.：没有猫。
?：可能有猫，有猫和没有猫的概率相同。

每个盒子

i

都有一条连向

b[i]

盒子的通道。

现在，从

1

到

n

对于每个盒子

i

依次执行操作：

如果盒子 $i$ 里没有猫或盒子 $b[i]$ 里有猫，不执行操作。
否则，盒子 $i$ 中的猫移动到盒子 $b[i]$ 中。

求盒子

n

中有猫的方案数（对于可能有猫的状态）。

分析

方案数不好算，我们可以转为算概率，最终方案数就是：盒子

n

中有猫的概率

\times

2

的 “ ? 的个数次幂”。

可以转为图论模型：每个点

i

都有一条连向

b[i]

的有向边。

那么一共有

n

条边，显然构成了 基环树。

一般基环树的题目都是从树上问题开始，最后特殊讨论环上情况，我们这里也使用这种思路。

如果没有环，也就意味着 无后效性。

那么我们可以从

1

到

n

枚举

i

，对于每条

i

连向

b[i]

的有向边，进行转移。

设盒子里有猫的概率为

a[i]

。

那么初值有：

\begin{cases} a[i] = 1 & (s[i] = \text{C}) \\ a[i] = 0 & (s[i] = \text{.}) \\ a[i] = \frac{1}{2} & (s[i] = \text{?}) \end{cases}

对于转移，分类讨论即可。对于

i

连向

b[i]

的边，得到：

$a[i] = a[i] \times a[b[i]]$ （ $i,b[i]$ 都有猫时， $i$ 才会有猫）
$a[b[i]] = a[i] \times (1-a[b[i]]) + a[b[i]] = a[i] + a[b[i]] - a[i] \times a[b[i]]$ 。

注意转移前先用两个变量存一下

a[i],a[b[i]]

的值，再用这两个变量转移。

接下来看环。

发现对于环上编号最小的点

c

，一定是最先被遍历到的。

此时断开

c

指向

b[c]

的边，枚举

a[c],a[b[c]] \in \{0,1\}

继续统计答案即可。

为什么断开

c

到

b[c]

的边是对的？

因为

c

是第一个到达的环上的点，因此现在重置

c,b[c]

的

a

的取值，并把前面的状态存起来，这样就可以避免从环上再绕一圈回到

c

时重复统计了刚刚存起来的状态。

这样就容易理解为什么不能断开其他边，因为都会使得

c

前面的状态重复统计。

理解了这点，这题就不难了。

CPP

#include <bits/stdc++.h>
using namespace std;
#define intt long long
const intt mod = 1000000007;
const intt inv2 = 500000004;
const int N = 5005;
int t,n,b[N],c;
intt a[N],ans,fu,fv,res,w;
char s[N];
bool vis[N];
stack<int> st;
void dfs(int u)
{
	if (vis[u])
	{
		c = u;
		while (st.size())
		{
			int v = st.top();
			c = min(c,v);
			if (v == u) break;
			st.pop();
		}
		while (st.size()) st.pop();
		return;
	}
	vis[u] = 1;
	st.push(u);
	dfs(b[u]);
}
int main()
{
	scanf("%d",&t);
	for (int T=1;T<=t;T++)
	{
		scanf("%d",&n);
		scanf("%s",s+1);
		for (int i=1;i<=n;i++) scanf("%d",&b[i]);
		memset(vis,0,sizeof(vis));
		res = 1; ans = 0;
		dfs(n);
//		cout << "c: " << c << endl;
		for (int p1=0;p1<=1;p1++)
		{
			for (int p2=0;p2<=1;p2++)
			{
				w = 1;
				for (int i=1;i<=n;i++) 
				{
					if (s[i] == '.') a[i] = 0;
					else if (s[i] == 'C') a[i] = 1;
					else a[i] = inv2;
				}
				for (int i=1;i<=n;i++)
				{
					if (i == c)
					{
						if (p1 == 0) a[c] = (1-a[c]+mod)%mod;
						if (p2 == 0) a[b[c]] = (1-a[b[c]]+mod)%mod;
						w = a[c] * a[b[c]] % mod;
						a[c] = p1; a[b[c]] = p2;
					}
					fu = a[i]; fv = a[b[i]];
					a[i] = fu * fv % mod;
					a[b[i]] = ((fv + fu - fu * fv % mod) % mod + mod) % mod;
				}
				ans = (ans + w*a[n] % mod) % mod;
			}
		}
		for (int i=1;i<=n;i++)
		{
			if (s[i] == '?') res = res * 2 % mod;
		}
		res = res * ans % mod;
		printf("Case #%d: %lld",T,res);
		puts("");
	}
	return 0;
}

题解：P13004 [GCJ 2022 Finals] Schrödinger and Pavlov

文章操作

题意

分析

相关推荐

评论

题解：P13004 [GCJ 2022 Finals] Schrödinger and Pavlov