飞太慢会落单/太快会受伤
jun头吉吉
·
·
题解
题意
给定一个长度为 n 的环。x 表示某一个点顺时针走 x 的距离。
会投掷 $n-1$ 次奶酪，每次：
- 随机选一个 $0\sim n-1$ 的整数 $y$，$y=i$ 的概率为 $a_i/100$。
- 从 $y$ 位置投掷奶酪。奶酪会以顺时针方向沿圆周前进。当奶酪遇到一只老鼠时：
- $1/2$ 的概率老鼠吃掉奶酪。奶酪和老鼠一起消失。
- $1/2$ 的概率什么都不做。
- 奶酪一直前进，直到消失。
对于每个整数 $0\le k\le n-1$，请输出坐标为 $k + 0.5$ 的老鼠没有吃奶酪的概率模 $998244353$ 的值。
$1\le n \le 40,\ 0\le a_i,\ \sum_{0\le i \le n-1}a_i = 100$。
## 题解
考虑 $(a,b)$ 表示 $a$ 奶酪到了 $b$ 老鼠前面。那么判定就类似于这样：
$$
\begin{aligned}
&(1,a_{1,1}),(1,a_{1,2}),\dots,(1,a_{1,p_1})\\
&(2,a_{2,1}),(2,a_{2,2}),\dots,(2,a_{2,p_2})\\
&\dots\\
&(n-1,a_{n-1,1}),(n-1,a_{n-1,2}),\dots,(n-1,a_{n-1,p_{n-1}})
\end{aligned}
$$
每次判定提供 $\frac12$ 的贡献。最后一次判定是被吃掉了。
然后这个是原题的判定顺序，一个结论是在保持 $(i,a_{i,1}),\dots,(i,a_{i,p_i})$ 顺序不变的前提下，我们可以任意的顺序判定。
考虑交换两次相邻的判定。如果两次判定的奶酪不同，那么交换显然没有影响。如果相同，设为 $(x,a)$ 和 $(y,a)$，但是都没有吃，也没有影响。唯一有影响的就是前一个没吃后一个吃了。发现交换后我们可以还是判定前一个没吃后一个吃了，然后把后面所有的 $(x,*)$ 改成$(y,*)$。
那么实际上就相当于我们可以同时把所有奶酪都放好，然后每次选一个奶酪走，这样答案是不变的。
然后我们不妨设要计算 $0.5$ 位置的老鼠没有吃到奶酪的概率。那么我们可以先让所有奶酪顺时针走到 $0$ 的位置并判定。这个过程可以用dp描述，设 $f_{i,j,k}$ 表示处理到过程 $i$，现在已经放了 $j$ 块奶酪，被吃了 $k$ 块的贡献和。（过程就形如 在 $1$ 加入奶酪，判定 $1.5$ 的老鼠，在 $2$ 加入奶酪，判定 $2.5$ 的老鼠，……，在 $n$ 加入奶酪）
如果当前是加入奶酪，如果概率是 $A_p$，那么转移就是：
$$
f_{i+1,j+w,k}\leftarrow f_{i,j,k}\times A_p^w/w!
$$
要除 $w!$ 是因为这 $n-1$ 块奶酪最后要按顺序放下去，要乘上重排数。
然后当前是判定老鼠，那么转移是：
$$
\begin{aligned}
&f_{i+1,j,k}\leftarrow f_{i,j,k}\times 1/2^{j-k}\\
&f_{i+1,j,k+1}\leftarrow f_{i,j,k}\times\left(1-1/2^{j-k}\right)
\end{aligned}
$$
然后现在全部在 $0$ 位置了，设现在有 $k$ 块奶酪和 $k+1$ 只老鼠，我们可以依次判定每块奶酪。我们考虑第一块不被 $0.5$ 吃掉的概率，发现就是：
$$
\left(\frac1{2^2}+\frac1{2^3}+\dots+\frac1{2^{k+1}}\right)\times \left(1+\frac1{2^{k+1}}+\frac1{2^{2(k+1)}}+\dots\right)
$$
第一部分就是一圈内被不是 $0.5$ 的老鼠吃掉的概率。然后每次有 $1/2^{k+1}$ 的概率没有吃就要进入下一圈。
第二块奶酪实际上是 $k$ 只老鼠的情况，然后一直到两只老鼠的情况。
上面的先化简是：
$$
\frac{2^k-1}{2^{k+1}-1}
$$
所以最后的概率就是：
$$
\prod_{i=1}^{k}\frac{2^i-1}{2^{i+1}-1}=\frac{1}{2^{k+1}-1}
$$
所以最后的答案就是：
$$
\sum f_{lst,n-1,i}\times (n-1)!/(2^{n-i}-1)
$$
单次复杂度 $\mathcal O(n^4)$，总复杂度为 $\mathcal O(n^5)$。
## 代码
```cpp
const int N=41;
int n;mint ans[N],a[N],dp[2][N][N];
mint fac[N],ifac[N],pw[N];
signed main(){
fac[0]=ifac[0]=pw[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i,pw[i]=pw[i-1]*2,ifac[i]=1/fac[i];
read(n);for(int i=0;i<n;i++)read(a[i]),a[i]/=100;
for(int X=0;X<n;X++){
memset(dp,0,sizeof dp);int cur=0,pre=1;
dp[cur][0][0]=1;
for(int i=1;i<=n;i++){
swap(pre,cur);memset(dp[cur],0,sizeof dp[cur]);
for(int j=0;j<n;j++)for(int k=0;k<=j;k++)if(dp[pre][j][k].x){
mint v=dp[pre][j][k];
for(int w=0;j+w<n;w++,v*=a[(X+i)%n])dp[cur][j+w][k]+=v*ifac[w];
}
if(i==n)break;
swap(pre,cur);memset(dp[cur],0,sizeof dp[cur]);
for(int j=0;j<n;j++)for(int k=0;k<=j;k++)if(dp[pre][j][k].x){
mint _=1/pw[j-k];
dp[cur][j][k]+=dp[pre][j][k]*_;
dp[cur][j][k+1]+=dp[pre][j][k]*(1-_);
}
}
mint ans=0;
for(int i=0;i<n;i++)ans+=fac[n-1]*dp[cur][n-1][i]/(pw[n-i]-1);
write(ans.x);pc(" \n"[X+1==n]);
}
}
```