SRM532 Div1(450) DengklekBuildingRoads

DengklekBuildingRoads

K≦8という制限がある。先頭の家から順に、自分より小さいに家との間にのみ道路を繋ぐとすると、直前K個の街の道路数の偶奇ごとに覚えておけば良い。道路を繋ぐ前のK個の家の道路の偶奇と、道路を繋いだ後の偶奇を決めると、それぞれの家に偶数本奇数本どちらの道路を繋ぐかが決まる。奇数本の道路を繋ぐ家にまず１本道路を繋いで、あとx本の道路をy個の家に繋ぐとすると、その方法は_x/2+yC_y。

時間計算量はO(NM²2^2K)でギリギリ。最大ケースで1.8秒。ある家から、直前K個の家に一気に道路を繋ぐのではなく、遠い家から順に繋いでいき、何個前の家まで繋いだかごとにもメモすると、高速化できるし、プログラムも簡単になるらしい。

#include <string>
#include <vector>
using namespace std;

int countbit( int n )
{
    n = ( n & 0x55555555 ) + ( n >> 1 & 0x55555555 );
    n = ( n & 0x33333333 ) + ( n >> 2 & 0x33333333 );
    n = ( n & 0x0f0f0f0f ) + ( n >> 4 & 0x0f0f0f0f );
    n = ( n & 0x00ff00ff ) + ( n >> 8 & 0x00ff00ff );
    n = ( n & 0x0000ffff ) + ( n >>16 & 0x0000ffff );
    return n;
}

long long MOD = 1000000007LL;
long long C[100][128];
vector<vector<vector<int> > > memo;
int N, M, K;

//  n: 注目している家
//  m: 残りの道路数
//  k: 直前K個の家の道路数の偶奇
int BT( int n, int m, int k )
{
    if ( n>=N )
        return m==0 && k==0 ? 1 : 0;
        
    if ( memo[n][m][k]!=-1 )
        return memo[n][m][k];

    unsigned long long ans = 0;

    for ( int kk=0; kk<(1<<min(K-1,n)); kk++ )
    {
        int c = countbit(kk^k);
        if ( c<=m )
        {
            int t = min(K,n)-1;
            for ( int i=c; i<=m; i+=2 )
                ans += C[(i-c)/2+t][t]*BT(n+1,m-i,kk<<1|c&1);
            ans %= MOD;
            
        }
    }

    return memo[n][m][k] = (int)ans;
}

class DengklekBuildingRoads{public:
int numWays( int N, int M, int K )
{
    for ( int i=0; i<100; i++ )
    {
        C[i][0] = C[i][i] = 1;
        for ( int j=1; j<i; j++ )
            C[i][j] = (C[i-1][j-1]+C[i-1][j])%MOD;
    }

    ::N = N, ::M = M, ::K = K;
    memo = vector<vector<vector<int> > >( N, vector<vector<int> >( M+1, vector<int>(1<<K,-1) ) );
    
    return BT( 1, M, 0 );
}};