题解：P12061 [THUPC 2025 决赛] 喜爱之钥
cyffff
·
·
题解
\text{Link}
场上被三元链硬控导致没时间做这道题了！
题意
有 k 个人进行游戏，初始局面有 n 把锁以及只能打开对应锁的 n 把钥匙，此外还有 m 把无法打开任何锁的假钥匙，所有 n+m 把无法分辨的钥匙被均匀随机地打乱。
现在 k 人轮流进行操作，每一人可选择一把钥匙与一把锁进行尝试，在场所有人均可知道尝试结果。每一把锁只能打开一次，当所有锁均被打开后游戏结束。
每人的操作策略均为选取最大概率可开锁的组合。若有多组组合均有最大概率，则均匀随机地采用一种。
问游戏过程中，每个人打开的锁的数量的期望，对 10^9+7 取模。
## 题解
不妨将概率问题转为计数问题以方便讨论。补上 $m$ 把假锁，与假钥匙一一对应，则每个 $1\sim n+m$ 的排列 $p_{1\sim n+m}$ 均描述一个状态，其中第 $i$ 把锁对应第 $p_i$ 把钥匙。
初始时任意一把锁打开任意一把钥匙的概率均为 $\dfrac{1}{n+m}$，不妨记第一个人用第一个钥匙开第一把锁并失败，这提供了 $p_1\ne 1$ 的信息。
接下来第二个人：
- 用第 $x$ 把钥匙开第一把锁，概率为 $\dfrac{1}{n+m-1}$，这代表 $p_1=x$ 的概率；
- 用第一把钥匙开第 $y$ 把锁，概率为 $\dfrac{1}{n+m-1}$，这代表 $p_y=1$ 的概率；
- 用第 $x$ 把钥匙开第 $y$ 把锁，概率为 $\dfrac{n+m-2}{(n+m-1)^2}$，这代表 $p_y=x$ 的概率，可通过容斥计算。
第二个人有 $n+m-1$ 种方案使用某把钥匙开第一把锁，$n-1$ 种方案使用第一把要是开另一把锁，故使用两种策略的概率分别可简单计算。
假设第二个人用第二把钥匙开第一把锁且失败，第三个人就只会继续用第三把钥匙开第一把锁，成功概率为 $\dfrac{1}{n+m-2}$。依此类推，接下来所有人会一直尝试解锁第一把锁。
设 $f_{n,m,x}$ 表示现有 $n$ 个锁以及 $n+m$ 个钥匙，当前轮到第 $x$ 个人操作。
- 若逐把试钥匙，一定会在 $n+m$ 次尝试中成功，概率为 $\dfrac{n+m-1}{2n+m-2}\cdot \dfrac{1}{n+m}$；
- 若逐把试锁：
- 若在 $n$ 次尝试中成功，则概率为 $\dfrac{n-1}{2n+m-2}\cdot\dfrac{1}{n+m}$；
- 否则该钥匙必定为假钥匙，概率为 $\dfrac{n-1}{2n+m-2}\cdot \dfrac{m}{n+m}$。
上述概率均可用排列计数方式来理解。前缀和优化转移到对应的状态并累加入对应状态答案即可。
无论成功还是失败，其都变为一个不含任何额外信息的子状态，可以转移。
时间复杂度 $O(nmk)$。
参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=5e3+10,M=50+5,mod=1e9+7;
inline int add(int x,int y){ return x+y>=mod?x+y-mod:x+y; }
inline int dec(int x,int y){ return x>=y?x-y:x-y+mod; }
inline void inc(int &x,int y){ x=add(x,y); }
int n,m,k,inv[N*2+M],f[N][M][M],fp[N][M][M],ansp[M];
inline void Prefix(int n){
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
inline void add(int n,int m,int l,int r,int v){
if(l>r||!v) return ;
inc(fp[n][m][l+1],v),inc(fp[n][m][r+2],mod-v);
if(r==k-1) inc(fp[n][m][0],v),inc(fp[n][m][1],mod-v);
inc(ansp[l],v),inc(ansp[r+1],mod-v);
}
inline void Add(int n,int m,int x,int c,int v){
if(x+c<=k) return add(n,m,x,x+c-1,v);
add(n,m,x,k-1,v),c-=k-x;
int cp=c/k;
add(n,m,0,k-1,1ll*cp*v%mod);
c-=cp*k;
add(n,m,0,c-1,v);
}
int main(){
k=read(),n=read(),m=read();
Prefix(n*2+m);
f[n][m][0]=1;
for(int i=n;i;i--)
for(int j=m;j>=0;j--)
for(int x=0;x<k;x++){
inc(fp[i][j][x+1],fp[i][j][x]);
int v=add(f[i][j][x],fp[i][j][x]);
if(!v) continue;
Add(i-1,j,x,i,1ll*v*inv[i+j]%mod);
int p=(x+i)%k;
if(j){
inc(f[i][j-1][p],1ll*v*(i-1)%mod*j%mod*inv[2*i+j-2]%mod*inv[i+j]%mod);
Add(i-1,j,p,j,1ll*v*inv[i+j]%mod*(i+j-1)%mod*inv[2*i+j-2]%mod);
}
}
for(int i=0,s=0;i<k;i++)
inc(s,ansp[i]),write(s),putc(' ');
flush();
}
```