本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-08 15:53:38

题解：AT_abc404_f [ABC404F] Lost and Pound

题目传送门

题意

题面真的太粪了。

给定 $n$ 个按钮，包括 $1$ 个好的按钮和 $n-1$ 个坏的按钮。进行 $T$ 轮游戏，每一轮将按钮随机打乱，并按 $m$ 次按钮（同一按钮可以按多次）。$n$ 轮游戏结束后，若好的按钮被按的次数不小于 $K$ 次，获胜。求获胜的最大概率。

思路

每一轮游戏中，按钮都被随机打乱，我们不知道好的按钮在哪里，也不清楚每一个按钮会按几次，所以我们可以枚举（说了跟没说一样）。发现 $m\le 30$，所以枚举可能出现的局面，即数的拆分。搜索发现 $p(30)=5604$。

在枚举按钮过后，可用动态规划解决概率问题。
令 $f_{i,j}$ 表示到第 $i$ 轮，好的按钮至少被按了 $j$ 次的概率，初始状态为 $f_{i,0}=1$。
在枚举了局面后，令 $cnt_e$ 表示当前局面，同一按钮被按了 $e$ 次的次数，可以得到 $$ f_{i,j} = \max_{\text {局面}}{\sum_{e=0}^{m} f_{i-1,\max(j-e,0)} \cdot \frac{cnt_e}{n}} $$ 最终答案 $f_{T,K}$，时间复杂度 $O(T\times m \times K \times p(m))$。

代码

#include<bits\/stdc++.h>
#define int long long
#define db long double
#define fi first
#define se second
#define F(i,l,r) for(int i=(l); i<=(r); i++)
using namespace std;
const int N = 1e6 + 50, M = 1e3 + 50;
const int INF=0x3f3f3f3f3f3f3f3f, mod=1e9+7;

int n,T,m,K,I;
int tot,cnt[40];
db f[40][40];

inline void calc(){
	if(tot>n) return ;
	cnt[0]=n-tot;
	F(j,1,K){
		db sum=0;
		F(e,0,m)
			sum += f[I-1][max(j-e,0ll)] * cnt[e] \/ n;
		f[I][j] = max(f[I][j], sum);
	}
}
inline void DFS(int t,int lst){
	if(!t) calc();
	F(i,max(1ll,lst), t){
		tot++;
		cnt[i]++;
		DFS(t-i,i);
		cnt[i]--;
		tot--;
	}
}
inline void work(){
	f[I][0]=1;
	tot=0;
	DFS(m,0);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>T>>m>>K;
	f[0][0]=1;
	F(i,1,T){
		I=i;
		work();
	}
	cout<<fixed<<setprecision(20)<<f[T][K]<<'\n';

	return 0;
}

完结撒花！