SRM562 Div2 Hard(900) RandomOption - kusano

レーンの組合わせと最右のレーンについて、苦手な組合わせを含まないレーンが何通りあるかを覚えれば、動的計画法で、苦手な組合わせを含まない全てのレーンの並べ方の総数が求められる。それをkeyCount!で割れば良い。

#include <vector>
using namespace std;

//  ビットカウント
int countbit( int n ) { int c=0; while(n)c+=n&1,n>>=1; return c; }

class RandomOption{public:
double getProbability( int keyCount, vector <int> badLane1, vector <int> badLane2 )
{
    int n = keyCount;
    vector<vector<bool> > C( n, vector<bool>( n, true ) );
    for ( int i=0; i<(int)badLane1.size(); i++ )
        C[badLane1[i]][badLane2[i]] = C[badLane2[i]][badLane1[i]] = false;

    vector<vector<long long> > T( 1<<n, vector<long long>(n) );
    for ( int i=0; i<n; i++ )
        T[1<<i][i] = 1LL;

    for ( int b=1; b<=n; b++ )
    for ( int i=0; i<(1<<n); i++ )
    if ( countbit(i)==b )
        for ( int a=0; a<n; a++ )
        for ( int b=0; b<n; b++ )
        if ( i>>a&1 && i>>b&1 && a!=b && C[a][b] )
            T[i][a] += T[i^1<<a][b];
    
    double ans = 0;
    for ( int i=0; i<n; i++ )
        ans += T[(1<<n)-1][i];
    for ( int i=1; i<=n; i++ )
        ans /= i;
    return ans;
}};