SRM457 Div1 Med TheHexagonsDivOne

問題概要

$1$ から $2N$ の数字の中から7つ選び出して6角形グリッドに書き込む。

隣接する全てのペア $a$, $b$ について $a \bmod N \neq b \bmod N$ が成立するような書き込み方の総数は何通りか求めよ。ただし回転して一致するものは同一とみなす。

制約

$ 1 \leqq N \leqq 150$

解法

まず中心に使う数字を決め打つとこれは $2N$ 通り。

隣接する数字の余りの条件から、残りの6個は $2(N-1)$ 個の中から選ぶことになる。以下用いる数字のmod Nにおける種類数で場合分けをする。

(1) 種類数6の場合(abcdef)

数字の選び方は $\frac{2^{6}(N-1)(N-2)(N-3)(N-4)(N-5)(N-6)}{6!}$ 通り

これを円形に並べる方法は $\frac{2^{6}(N-1)(N-2)(N-3)(N-4)(N-5)(N-6)}{6!} \cdot 5!$ 通り

(2) 種類数5の場合(aabcde)

数字の選び方は $\frac{2^{4}(N-1)(N-2)(N-3)(N-4)(N-5)}{4!}$ 通り

a同士が隣り合わないようにするためには abcde で円順列を形成して残る3つの隙間のうち一つを選べば良い

よって $\frac{2^{4}(N-1)(N-2)(N-3)(N-4)(N-5)}{4!}\cdot 4! \cdot 3$ 通り

(3) 種類数4の場合(aabbcd)

数字の選び方は $\frac{2^{2}(N-1)(N-2)(N-3)(N-4)}{2!2!}$ 通り

a同士が隣り合わない配置として次が挙げられる

• a?a???
• a??a??

前者は aba??? と a?ab?b を考えて、 $2(2 \cdot 3!+2! \cdot 2!)=32$ 通り

後者はb同士が隣り合う余事象を引くことを考えて、 $4! - 2 \cdot 2! \cdot 2! =16$ 通り

以上より $\frac{2^{2}(N-1)(N-2)(N-3)(N-4)}{2!2!} \cdot 48$ 通り

(4) 種類数3の場合(aabbcc)

数字の選び方は $\frac{(N-1)(N-2)(N-3)}{3!}$ 通り

(3)同様にaの位置関係で場合分けをする

前者は $2(2 \cdot 2! \cdot 2! ) = 16$ 通り

後者は $4! - 2 \cdot 2! \cdot 2! =16$ 通り

以上より $\frac{(N-1)(N-2)(N-3)}{3!} \cdot 32$ 通り

後はこれを実装すれば良い。

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

class TheHexagonsDivOne {
    public:
    long long count(int n) {
        auto calc=[](ll n)->ll{
            ll res=0;
            res+=64*n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)/6;
            res+=48*n*(n-1)*(n-2)*(n-3)*(n-4);
            res+=48*n*(n-1)*(n-2)*(n-3);
            res+=32*n*(n-1)*(n-2)/6;
            return res;
        };
        return calc(n-1)*2LL*(ll)n;
    }
};

感想

久しくこういうの真面目に書いてなかったなと思い、実際バチャ中にも時間かけてしまった反省もあったので書いてみた。