多校A层冲刺NOIP2024模拟赛03 -- T4 量子隧穿问题
感觉是这两天最有意义的题吧。
\(n\) 句话题意
我是巴甫洛夫的狗，我又重生了，重生在薛定谔的家里。
薛定谔是抖S，于是给我铃声。我开始狂跑不止。
为什么没流口水没删除我
给定 \(n\) 个点，对于 \(i\) 存在一条外向连的单向边。对于每个点，存在三种状态，有人无人不确定。
将 \(i\) 从小到大遍历，对于第 \(i\) 个点若存在人，且下一个点无人，则这人将沿边跑到下一个点，否则不动。
对于不确定的点，可能是有人也可能是没人，问有多少种在遍历完最后一个盒子有人的情况。 \(n \le 5000\) (其实 \(1e6\) 大差不差也能过)
题解
这个题就是纯唐。首先我们发现捏，这个东西显然是一个内向基环树。
然后我们不考虑基环树，就考虑普通树，普通树怎么做？
我们发现如果是概率的话，每个点的概率显然就是 \(0\)（无人），\(1\)（有人），\(\frac{1}{2}\)（不确定）。
好像这个可以搞诶……
那么对于一次转移，即从 \(i\) 到其父亲节点，若以 \(k_1\) 表示 \(i\) 点概率， \(k_2\) 表示 \(fa_i\) 的概率。（转移前）
则转移后新概率：
\[\begin{aligned} k_1' &= k_1 \times k_2 \\ k_2' &= (1 - k_2) \times k_1 + k_2 \end{aligned}\]感觉还是挺显然的……
那只用从小往大依次枚举就好了呀，做完了。
好的，现在来看正解。
那有些长得帅的小伙伴就会问了，这和树有啥区别吗？难道把边重新跑一遍有啥区别吗？
诶，现在有这么一个环：
1 -> 2
\ / (2 -> 3 , 3 -> 1)
3
如果 \(1 , 2 , 3\) 全是 \(?\) ， 那么对于 \(2\) 来说 \(2\) 是 \(0\) ，\(1\) 号有可能 \(1/0\) , \(3\) 同理，对于处理 \(1 \to 3\)，时，可能钦定 \(1\) 号为 \(1\)，然而 \(3\) 号可能是由 \(1\) 号为 \(0\) 转移来的。因此有错误。
那有些长得帅的小伙伴们又会说了，不是那咋做？
我们发现错误的原因是由于第一个点重复了，那我们钦定第一个值是啥，那不就不会重复了吗！
只要我们钦定这个环里第一次处理的边的值并确定之，最后乘上其为被钦定的值的概率，加起来，乘总数，就得到答案了。时间复杂度 \(\mathcal{O(n)}\)
完结撒花！！！
Code
CODE
#include <bits/stdc++.h>
typedef long long ll ;
using namespace std ;
const int N = 5010 ;
const int mod = 1e9 + 7 ;
int T , n ;
char s[N] ; int b[N] ;
struct Node {
int father[N] ; ll Probabit[N] ;
inline void clear(int n) {
for (int i = 1 ; i <= n ; ++ i) father[i] = i ;
for (int i = 1 ; i <= n ; ++ i) {
if (s[i] == '.') Probabit[i] = 0 ;
else if (s[i] == 'C') Probabit[i] = 1 ;
else Probabit[i] = (mod + 1) / 2 ;
}
}
int Find_Father(int x) {
if (x == father[x]) return x ;
return father[x] = Find_Father(father[x]) ;
}
bool Combine(int x , int y) {
return Find_Father(x) == Find_Father(y) ;
}
bool Merge(int x , int y) {
x = Find_Father(x) , y = Find_Father(y) ;
if (x == y) return true ;
return father[y] = x , false ;
}
} ;
struct Probability {
ll Probabit[N] ;
inline void clear(int n) {
for (int i = 1 ; i <= n ; ++ i) {
if (s[i] == '.') Probabit[i] = 0 ;
else if (s[i] == 'C') Probabit[i] = 1 ;
else Probabit[i] = (mod + 1) / 2 ;
}
}
void Build_Bridge(int x , int y) {
ll fir = Probabit[x] , sec = Probabit[y] ;
Probabit[y] = ((1 - sec + mod) * fir + sec) % mod ;
Probabit[x] = (fir * sec) % mod ;
}
ll Ask() {
ll ans = 0 ;
for (int i = 1 ; i <= n ; ++ i) {
if (s[i] == '?') ans = (ans * 2ll) % mod ;
}
return (ans * Probabit[n]) % mod ;
}
Probability operator = (Probability b) {
for (int i = 1 ; i <= n ; ++ i) {Probabit[i] = b.Probabit[i] ; }
return b ;
}
} ;
Node alpha , beta ; Probability theta , delta ;
signed main() {
freopen("experiment.in" , "r" , stdin) ;
freopen("experiment.out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
cin >> T ;
while (T --) {
cin >> n >> s + 1 ;
for (int i = 1 ; i <= n ; ++ i) cin >> b[i] ;
alpha.clear(n) , beta.clear(n) ; int xrlong = 0 ;
for (int i = 1 ; i <= n ; ++ i) alpha.Merge(i , b[i]) ;
for (int i = n ; i >= 1 ; -- i) {
if (alpha.Combine(i , n) && beta.Merge(i , b[i])) {
xrlong = i ;
}
}
theta.clear(n) ;
if (!xrlong) {
for (int i = 1 ; i <= n ; ++ i) {
theta.Build_Bridge(i , b[i]) ;
}
cout << theta.Ask() << '\n' ;
continue ;
} else {
ll ans = 0 ;
char s1 = s[xrlong] , s2 = s[b[xrlong]] ; ll p1 , p2 ;
for (int i = 1 ; i < xrlong ; ++ i) theta.Build_Bridge(i , b[i]) ;
p1 = theta.Probabit[xrlong] , p2 = theta.Probabit[b[xrlong]] ;
for (int x = 0 ; x <= 1 ; ++ x) {
for (int y = 0 ; y <= 1 ; ++ y) {
ll now = 1 ;
delta = theta ; delta.Probabit[xrlong] = x ;
delta.Probabit[b[xrlong]] = y ;
now = ((x == 0 ? 1 + mod - p1 : p1) * (y == 0 ? 1 + mod - p2 : p2)) % mod ;
for (int i = xrlong ; i <= n ; ++ i) {
delta.Build_Bridge(i , b[i]) ;
}
now = (now * delta.Probabit[n]) % mod ; (ans += now) %= mod ;
}
}
for (int i = 1 ; i <= n ; ++ i)
if (s[i] == '?') ans = (ans * 2) % mod ;
cout << ans << '\n' ;
}
}
}