[ACM] hihoCoder 1075 開鎖魔法III （動態規劃，組合數學）

4
5 1
2 5 4 3 1
5 2
2 5 4 3 1
5 3
2 5 4 3 1
5 4
2 5 4 3 1

0.000000000
0.600000000
0.900000000
1.000000000

做這種題真是頭疼，沒思路無從下手，還是做的題少再加上沒有仔細得分析，下面就來好好得分析一下本題。

1.只要打開一個盒子，那麼就能打開一連串的盒子，因為打開的盒子裡面有著另一個盒子的鑰匙。

2.要求全部盒子打開的概率，那麼用 全部盒子可以打開的方法除以總的方法數就可以了。 總的方法數好求，就是C（n,k)，即在n個盒子中選擇k個打開。

對於第一點，打開一連串的盒子，那麼最後一個盒子裡的鑰匙一定是第一個打開盒子的鑰匙，比如首先打開2號盒子，那麼陸續打開x個盒子以後，

突然發現最後打開的那個盒子裡面是2號盒子的鑰匙，那麼這一連串打開就結束了，也就構成了一個循環。所以很容易聯想到組合數學中置換群的循

環節。所以就把所有的循環節都找出來。比如一共有num個循環節，那麼能打開全部盒子的條件為給定的鑰匙個數k一定要大於等於num，否則最少

有一個循環節裡不能打開一個盒子。

對於第二點，求可以打開的方法數采用動態規劃遞推的方法。首先劃分階段，前面說到一共有num個循環節，那麼就把整個問題劃分為num個階

段，每次循環解決一個階段的問題。接下來是定義狀態 ，用dp[ i ] [ j ] ，表示用j把鑰匙打開前i個階段的盒子一共有多少種方法。用到乘法原理，乘

法遠離是第一個階段有a種選擇，第二個階段有b種選擇，那麼前兩個階段一共有a*b種選擇。這裡要用到。用遞推就要考慮狀態的轉移：比如當前是

dp [ i ] [ j] ， 那麼前一個狀態為 dp [ i -1] ] [ j - use ] , 即用j-use把鑰匙打開前i-1個階段的盒子一共有的方法數，也就是說打開第i個階段的盒子用了

use個鑰匙，一共有 C(cnt,use)種方法，cnt為第i個階段一共有cnt個待打開的盒子。那麼根據乘法原理 dp[i][j]=dp[i-1][j-use]*C(cnt,use) ，但是前一

個狀態不唯一，也就是use的值可以變化，所以要方法累加 即dp[i][j]+=dp[i-1][j-use]*C(cnt,use). 這裡dp[i][j]是未知的，要求它就必須知道dp[i-1][j-

use]，也就是用已知的狀態去推出未知的狀態。

這裡用一個例子具體說明一下： 比如一共可以劃分為2個階段，第一個階段有2個盒子，第二階段有3個盒子，而給定的鑰匙數k為3.

初始dp [ 0 ] [ 0 ] =1;

dp[1][1]+=dp[0][0]*c[2][1] , 第一個階段裡有2個盒子，只用一把鑰匙，任選一個盒子開開，一共有c[2][1]種方法

dp[1][2]+=dp[0][0]*c[2][2], 用兩把鑰匙，只有一種方法

階段1已求完，用已知的數據去推出未知

dp[2][2]+=dp[1][1]*c[3][1], 乘法原理，第一階段用了1把鑰匙，第二階段使用一把鑰匙，去開第二階段的3個盒子，任選1個 C[3][1]種方法

dp[2][3]+=dp[1][1]*c[3][2]; 第二階段使用兩把鑰匙，去開第二階段的3個盒子，任選2個C[3][2]種方法

dp[2][3]+=dp[1][2]*c[3][1]; 第一階段用了2把鑰匙，第二階段使用一把鑰匙，去開第二階段的3個盒子，任選1個C[3][1]種方法

到此本題就分析完了。

值得特別注意的是，最後要用可行方法數除以總的方法數，考慮到精度問題，分子為dp [cnt ][k] 設置為double， 分母組合數也設置成double ，很容易出錯。

代碼：

#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,k;
int match[320];
double c[320][320];
bool vis[320];
double dp[320][320];
vectorloop;

void getComb()
{
    for(int i=0;i<=300;i++)
    {
        c[i][0]=c[i][i]=1.0;
        for(int j=1;j>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>match[i];
            
        loop.clear();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)//求循環節
        {
            if(vis[i])
                continue;
            int cnt=0,cur=i;
            while(!vis[cur])
            {
                cnt++;
                vis[cur]=1;
                cur=match[cur];
            }
            loop.push_back(cnt);
        }
        
        int num=loop.size();
        if(k