AtCoder ABC 065 C - Reconciled? (5Q, 茶色, 300 点)

数学 IA でもありがちな問題！

• 問題へのリンク

問題概要

匹の犬 と、 引の猿 を一列に並べる。

犬同士・猿同士がそれぞれ隣り合わないように並べる方法の数を 1000000007 で割った余りを求めよ。

制約

• 

考えたこと

実は、 や の場合は、条件を満たすように並べることができない。

のとき（犬が 1 匹多いとき）

この場合は、下図のように、犬を両端において、犬と猿を交互に並べるしかない。

犬自体の並べ方は 通り、猿自体の並べ方は 通りあるから、全部で

---

通り

---

である。

のとき（猿が 1 匹多いとき）

この場合も同様に、猿を両端に並べて、猿と犬を交互に並べるしかない。犬自体の並べ方は 通り、猿自体の並べ方は 通りあるから、全部で

---

通り

---

である。

のとき（猿と犬が同数のとき）

この場合は、下図のように、犬からスタートする場合と猿からスタートする場合がある。

それぞれについて、犬自体の並べ方は 通り、猿自体の並べ方は 通りあるから、全部で

---

通り

---

である。

コード

上記は の計算量で実装できる。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main() {
    long long N, M;
    cin >> N >> M;

    // N! と M! の積を求めておく
    long long nfuct = 1, mfuct = 1;
    for (long long i = 1; i <= N; i++) nfuct = nfuct * i % MOD;
    for (long long i = 1; i <= M; i++) nfuct = nfuct * i % MOD;
    long long res = nfuct * mfuct % MOD;

    if (abs(N - M) >= 2) {
        cout << 0 << endl;
    } else if (abs(N - M) == 1) {
        cout << res << endl;
    } else {
        cout << res * 2 % MOD << endl;
    }
}