SRM457 Div1 Medium(500) TheHexagonsDivOne

TheHexagonsDivOne

7個の数字を選びルールに従って配置するとき、a%n==b%nが成り立つ組が同数であれば並べ方の通りも同じである。例えばn=10のとき、{1,2,3,4,5,6,11}と{4,5,6,7,8,9,19}はa%n==b%nが成り立つ組が１つなので、どちらも並べ方は同数。
↓のプログラムでa%n==b%nが成り立つ組がk組あった場合の並べ方を数える。

long long TheHexagonsDivOne::sub( int n, int v[7] )
{
    long long ans = 0;

    //  1 2
    // 6 0 3
    //  5 4
    const int adj[7][7] = 
    {
        { 0, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 0, 0, 0, 1 },
        { 1, 1, 0, 1, 0, 0, 0 },
        { 1, 0, 1, 0, 1, 0, 0 },
        { 1, 0, 0, 1, 0, 1, 0 },
        { 1, 0, 0, 0, 1, 0, 1 },
        { 1, 1, 0, 0, 0, 1, 0 },
    };

    sort( v, v+7 );

    do
    {
        bool f = true;

        for ( int i=0; i<7; i++ )
        for ( int j=i+1; j<7; j++ )
            if ( adj[i][j] != 0  &&
                 v[i]%n == v[j]%n )
                f = false;

        if ( f )
            ans++;
    }
    while ( next_permutation( v, v+7 ) );

    return ans / 6;
}

int main() {
    TheHexagonsDivOne test;

    int n = 10;
    int v0[7] = {  1,  2,  3,  4,  5,  6,  7 };
    int v1[7] = {  1,  2,  3,  4,  5,  6, 11 };
    int v2[7] = {  1,  2,  3,  4,  5, 11, 12 };
    int v3[7] = {  1,  2,  3,  4, 11, 12, 13 };

    cout << test.sub( n, v0 ) << endl;
    cout << test.sub( n, v1 ) << endl;
    cout << test.sub( n, v2 ) << endl;
    cout << test.sub( n, v3 ) << endl;
}

k=0,1,2,3のとき値はそれぞれ840,360,144,32。
2n個の中からa%n==b%nがk組成り立つような組み合わせは、
n組の(i,i+n)の中からk組選ぶのがcomb(n,k)通り、
残りn-k組から7-2*k組選ぶのがcomb(n-k,7-2*k)通りで、それぞれにiかi+nかで2通り。

class TheHexagonsDivOne
{
public:
    long long count( int n );
    long long comb( int n, int m );
};

long long TheHexagonsDivOne::count( int n )
{
    int c[4] = { 840, 360, 144, 32 };

    long long ans = 0;
    for ( int k=0; k<=3; k++ )
        ans += c[k] * comb(n,k) * comb(n-k,7-2*k) * (1ll<<(7-2*k));

    return ans;
}

long long TheHexagonsDivOne::comb( int n, int m )
{
    if ( n < m )
        return 0;

    long long r = 1;

    for ( int i=0; i<m; i++ )
        r *= n-i;
    for ( int i=1; i<=m; i++ )
        r /= i;

    return r;
}