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

· · 题解

题意

有 n 个盒子，每个盒子都有一个状态 s[i]：

每个盒子 i 都有一条连向 b[i] 盒子的通道。

现在，从 1 到 n 对于每个盒子 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[b[i]] 的值，再用这两个变量转移。

接下来看环。

发现对于环上编号最小的点 c，一定是最先被遍历到的。

此时断开 c 指向 b[c] 的边，枚举 a[c],a[b[c]] \in \{0,1\} 继续统计答案即可。

:::info[为什么断开 c 到 b[c] 的边是对的？]{open}

因为 c 是第一个到达的环上的点，因此现在重置 c,b[c] 的 a 的取值，并把前面的状态存起来，这样就可以避免从环上再绕一圈回到 c 时重复统计了刚刚存起来的状态。

这样就容易理解为什么不能断开其他边，因为都会使得 c 前面的状态重复统计。

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


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