WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 5004: 开锁魔法II
BZOJ 5004: 开锁魔法II

题目大意

N个盒子N把钥匙一一对应,每个盒子里放一把钥匙。初始随机打开K个盒子,问最终所有盒子都能被打开的概率。

题解

原题相当于N个入度出度为1的点,会构成P个环。每个环至少需要在初始的时候被打开一个点就可以全部被打开。
DP[i][k]表示前i个环,使用了k次初始打开机会的概率。令cnt[i]为第i个环的大小,sum[i]=\sum_{k=i}^{k\leq P}cnt[i]
转移方程为:

DP[i][k]=\sum_{p=1}^{p\leq k} DP[i-1][k-p]\times \frac{C_{cnt[i]}^{p}\cdot C_{sum[i]-cnt[i]}^{K-k-p}}{C_{sum[i]}^{K-k}}

代码

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN=3e2+50;

int n, K;
int cnt[MAXN], tot;
int sum[MAXN];
int nxt[MAXN];
bool vis[MAXN];

double fac[MAXN];
double dp[MAXN][MAXN];

void dfs(int x){
    vis[x]=true; cnt[tot]++;
    if (!vis[nxt[x]]) dfs(nxt[x]);
}

inline double getComb(int n, int m){
    if (m>n || n<0 || m<0) return 0;
    return exp(fac[n]-fac[m]-fac[n-m]);
}

inline void solve(int T){
    scanf("%d%d", &n, &K);
    for (int i=1; i<=n; i++) scanf("%d", &nxt[i]);


    memset(vis, false, sizeof(vis));
    tot=0; for (int i=1; i<=n; i++) if (!vis[i]) cnt[++tot]=0, dfs(i);//, printf("%d ", cnt[tot]); printf("\n");
    sum[tot+1]=0; for (int i=tot; i>=1; i--) sum[i]=sum[i+1]+cnt[i];

    memset(dp, 0, sizeof(dp)); dp[0][0]=1;
    for (int i=1; i<=tot; i++){
        for (int k=0; k<K; k++){
            for (int p=1; p<=K-k && p<=cnt[i]; p++){
                if (K-k>sum[i]) continue;
                if (K-k-p>sum[i]-cnt[i]) continue;
                dp[i][k+p]+=dp[i-1][k]*getComb(cnt[i], p)/getComb(sum[i], K-k)*getComb(sum[i]-cnt[i], K-k-p);
                //printf("(%d, %d)->(%d, %d) %f\n",i-1, k, i, p+k, dp[i-1][k]*getComb(cnt[i], p)/getComb(sum[i], K-k)*getComb(sum[i]-cnt[i], K-k-p));
            }
        }
    }


    printf("%.9f\n", dp[tot][K]);
}

int main(){
    fac[0]=0; for (int i=1; i<MAXN; i++) fac[i]=fac[i-1]+log(i);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 5004: 开锁魔法II
题目大意 N个盒子N把钥匙一一对应,每个盒子里放一把钥匙。初始随机打开K个盒子,问最终所有盒子都能被打开的概率。 题解 原题相当于N个入度出度为1的点,会构成P个环。每个环至少需要…
扫描二维码继续阅读
2018-10-09
<--! http2https -->