【bzoj 5004】開錠魔法II組合せ数学+確率dp

タイトルの説明
$n$の箱があり、各箱には鍵が1つしかなく、各箱には鍵が1つしかなく、開くことができます.今ランダムに$m$の箱を開けて、すべての箱を開ける確率を求めます.
問題解
組合せ数学+確率dp
テーマは各点の入度と出度が1であることを約束しているので,最終的な図は必ずいくつかのリングである.各ループは、少なくとも1つの点を選択すると、要件を満たすことができます.
各ループの点数$c[i]$およびその接尾辞および$sum[i]$を前処理する.
$f[i][j]$は、前$i$個のループの中から$j$個の点が選択され、最終条件を満たす確率を表す.$f[0][0]=1$を初期化します.
$i$と前$i-1$リングの点数$j$、第$i$リングの点数$k$を列挙すると、$isim n$の合計スキーム数は$C_{sum[i]}^{m-j}$,条件を満たすシナリオ数$c[i]$のうち$k$個を選択したシナリオ数に残りの部分を乗じて$m-j-k$個を選択したシナリオ数$C_{c[i]}^k·C_{sum[i]-c[i]}^{m-j-k}$ .
整理するとdp方程式$f[i][j+k]leftarrow f[i-1][j]・frac{C_{c[i]}^k・C_が得られる{sum[i]-c[i]}^{m-j-k}}{C_{sum[i]}^{m-j}}$ .
最後の答えは$f[n][m]$です.
そのうち組合せ数は直接doubleを使って貯めることができるそうですが、私は弱いので、階乗の$ln$を貯めて、求めるときに$text{exp}$を返します.
時間複雑度$O(Tn^2)$

#include 
#include 
#include 
#include 
#define N 310
using namespace std;
int a[N] , c[N] , vis[N] , sum[N];
double fac[N] , f[N][N];
int main()
{
    int T;
    scanf("%d" , &T);
    while(T -- )
    {
        memset(vis , 0 , sizeof(vis));
        memset(f , 0 , sizeof(f));
        f[0][0] = 1;
        int n , m = 0 , p , i , j , k;
        scanf("%d%d" , &n , &p);
        for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , fac[i] = fac[i - 1] + log(i);
        for(i = 1 ; i <= n ; i ++ )
        {
            if(!vis[i])
            {
                c[++m] = 0;
                for(j = i ; !vis[j] ; j = a[j])
                    vis[j] = 1 , c[m] ++ ;
            }
        }
        sum[m + 1] = 0;
        for(i = m ; i ; i -- ) sum[i] = sum[i + 1] + c[i];
        for(i = 1 ; i <= m ; i ++ )
            for(j = max(i - 1 , p - sum[i]) ; j < p && j <= n - sum[i] ; j ++ )
                for(k = 1 ; k <= c[i] && j + k <= p ; k ++ )
                    f[i][j + k] += f[i - 1][j] * exp(fac[c[i]] + fac[sum[i] - c[i]] + fac[p - j] + fac[sum[i] - p + j] - fac[k] - fac[c[i] - k] - fac[p - j - k] - fac[sum[i] - c[i] - p + j + k] - fac[sum[i]]);
        printf("%.9lf
" , f[m][p]);
    }
    return 0;
}