Reconciled? [AtCoder Beginner Contest 065 / AtCoder Regular Contest 076 C]

http://arc076.contest.atcoder.jp/tasks/arc076_a

前提知識

• 組合せ数学の知識(modでfacをとれるかという部分)

hamayanhamayan.hatenablog.jp

解法

http://arc076.contest.atcoder.jp/submissions/1379791

高校数学の組合せの問題のようにして解く。
まず、犬同士と猿同士は隣にできないということは、2匹の数の差は0か1でないといけないと分かる。
この2つで場合分けして考えてみる。

差が0(同数)のとき

N = 3, M = 3であるならば、
「犬猿犬猿犬猿」とおくか「猿犬猿犬猿犬」とおくかの2通りある。
そして、犬の置き方は3!通り、猿の置き方は3!通りであるので、全部で2*3!*3!通りが答え。

つまり、2*N!*M!が答え

差が1のとき

N = 3, M = 2であるならば「犬猿犬猿犬」の1通りの置き方しかない。
そして、犬の置き方は3!通り、猿の置き方は2!通りであるので、全部で3!*2!通りが答え。

つまり、N!*M!が答え

あとは、これをmod10^9で答えれば良いが、愚直にmod10^9しながら、階乗を答えてしまえばいい。
（自分の解答でもmodで各種組み合わせ数を求めるライブラリがあるので、それを使って答えてしまっている）

Comb<mint, 201010> com;
int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
 
    mint ans = 0;
    
    if (M == N) ans = com.aPb(N, N) * com.aPb(M, M) * 2;
    else if (abs(N - M) == 1) ans = com.aPb(N, N) * com.aPb(M, M);
    else ans = 0;
 
    cout << ans.get() << endl;
}