今回の問題はデータの情報落ちとの戦いでした。。アルゴリズム自体はすぐにでてきて簡単に実装はできたのですが、longlong で素直に計算してもあれれ？これなぜ負の数がでてくるの？みたいな感じになってしまって結構大変でした。

では以下問題

問題

問題文

すぬけ君は、犬を N 匹と猿を M 匹飼っています。すぬけ君は、この N+M 匹を一列に並べようと思っています。

文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、犬同士、または猿同士が隣り合うところができないように並べようと思っています。

このような並べ方は何通りあるでしょうか。犬と猿は 10⁹+7 以上の数を理解できないので、並べ方の個数を 10⁹+7 で割ったあまりを求めてください。ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。

制約

* 1≦N,M≦10^5

と言うもの

愚直に配列用意してそこに犬いれて猿いれて。。なんてしていたら計算のオーダはN,Mが大きくなるにつれて階乗並みに増えていくので現実的ではない。。

考えたこと

犬と猿の交互の列が何個作れるかの問題なので、まず N と Mについての関係を紐解く交互にするためには、絶対値|N - M| は 1以下であることが必須条件になってくる。|N-M|=1の時はスワップを利用し考え、N - M = 0の時と分けて考えれば良いと言うことです。では次に列の種類の算出ですが、次のように考えましょう

文字列	1	2	3	4	5
累積配列	犬a	猿a	犬b	猿b	犬c

のような列ができるとします。これは一例なのでもっと抽象化しましょう

文字列	1	2	3	4	5
累積配列	犬	猿	犬	猿	犬

こうすれば数式が見えてくると思います。

1に入るのは a,b,c のどれか -> 組み合わせは 3×2×1 = 6
2に入るのは a,b のどれか -> 組み合わせは 2×1 = 2
3に入るのは1に入った以外の二つ -> 組み合わせは2×1 = 2
4に入るのは残った猿 -> 組み合わせは 1
5に入るのは残った犬 -> 組み合わせは1

これらは排反なので加算で列の種類数が算出できます。

フロー

入力の受け取り
もし N = Mである時
- Mの値を変数に格納する
- 答えを1とする
- N から 1 までループを回しながら
  - ループの変数とMの値の変数と答えを乗算し 10⁹ + 7の剰余をとる
  - Mの値の変数をデクリメント
- 答えを2倍する
- 答えに対して 10⁹ + 7の剰余をとる
- 答えの出力
もし N - 1 = M または M - 1 = N の時
- もし M - 1 = N の時
  - NとMをスワップ
- Nの値を変数に格納する
- 答えを1とする
- M から 1 までループを回しながら
  - ループの変数とNの値の変数を乗算し10⁹ + 7の剰余と 10⁹ + 7の剰余を乗算しその結果から 10⁹ + 7の剰余をとる
  - Nの値の変数をデクリメント
- 答えの出力
それ以外の時
- 0を出力する

とこんな感じ

プログラム

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main(void){
    long long N,M;
    cin >> N >> M;
    if (N == M){
        unsigned long long ans = 1;
        unsigned long long tmp = M;
        for(long long i = N;i > 0;i--){
            ans = (i * tmp * ans) % (1000000000 + 7);
            tmp--;
        }
        ans *= 2;
        ans = ans % (1000000000 + 7);
        cout << ans << endl;
    }else if(N - 1 == M || M - 1 == N){
        if(M - 1 == N){
            swap(N,M);
        }
        long long ans = 1;
        long long tmp = N;
        for(long long i = M;i > 0;i--){
            ans = ((i * tmp)% (1000000000 + 7) * (ans % (1000000000 + 7)) % (1000000000 + 7));
            tmp--;
        }
        cout << ans % (1000000000 + 7) << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}

xlkeiの日記

ABC-065 C Reconciled? を解いてみた

問題

問題文

制約

考えたこと

フロー

プログラム