自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 23:12:31，当前版本为作者最后更新于2025-04-18 10:47:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

场上被三元链硬控导致没时间做这道题了！

题意

有 $k$ 个人进行游戏，初始局面有 $n$ 把锁以及只能打开对应锁的 $n$ 把钥匙，此外还有 $m$ 把无法打开任何锁的假钥匙，所有 $n+m$ 把无法分辨的钥匙被均匀随机地打乱。

现在 $k$ 人轮流进行操作，每一人可选择一把钥匙与一把锁进行尝试，在场所有人均可知道尝试结果。每一把锁只能打开一次，当所有锁均被打开后游戏结束。

每人的操作策略均为选取最大概率可开锁的组合。若有多组组合均有最大概率，则均匀随机地采用一种。

问游戏过程中，每个人打开的锁的数量的期望，对 $10^9+7$ 取模。

$n\le 5000$，$m,k\le 50$。

题解

不妨将概率问题转为计数问题以方便讨论。补上 $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)$。

参考代码：

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