题解：AT_abc404_f [ABC404F] Lost and Pound

Handezheng · 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_{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;
}

完结撒花！