SRM457 Div2 Hard(1000) TheHexagonsDivTwo

TheHexagonsDivTwo

0≦t＜kを隣り合ったセルが異なるように配置する。それぞれの配置について、tが書かれたセルにはi%k=tとなる数字を置く場合の数を計算する。

#include <algorithm>

using namespace std;

class TheHexagonsDivTwo
{
    long long put( int n, int k, int hex[7], int p );
    long long perm( int a, int b );

public:
    long long count( int n, int k );
};

long long TheHexagonsDivTwo::count( int n, int k )
{
    int hex[7];

    return put( n, k, hex, 0 ) / 6;
}

long long TheHexagonsDivTwo::put( int n, int k, int hex[7], int p )
{
    long long ans = 0;

    if ( p == 7 )
    {
        long long a = 1;
        for ( int i=0; i<k; i++ )
            a *= perm( (n+i)/k, ::count(hex,hex+7,i) );

        ans += a;
    }
    else
    {
        for ( int i=0; i<k; i++ )
        {
            //  1 2
            // 6 0 3
            //  5 4
            if ( p >= 1  &&  i == hex[0]  ||
                 p >= 2  &&  i == hex[p-1]  ||
                 p == 6  &&  i == hex[1] )
                continue;

            hex[p] = i;
            
            ans += put( n, k, hex, p+1 );
        }
    }

    return ans;
}

long long TheHexagonsDivTwo::perm( int a, int b )
{
    long long n = 1;

    for ( int i=a; i>a-b; i-- )
        n *= i;

    return n;
}