解説

説明のため、N人の正直者を正直者1, 正直者2, ..., 正直者Nと呼ぶことにする。

円の数え上げの典型テクを使う
「1つを先頭として固定することで、列の数え上げにする」
先頭を正直者1と固定することにしよう。

今回の問題の条件を少しわかりやすく変えると、
「隣が同じなら正直者と返答する」つまり、「K個以上隣接が同じである組合せ」が答えになる。
ここで重要なのは、条件的には正直者や嘘つきの個々の区別は必要ないということ。
なので、先頭を正直者1として、他の正直者・嘘つきの『配置』の組合せを求める。
この答えに×(N-1)!×M!をすると、人を区別した、本当の答えになる。
よって、これ以降は、先頭を正直者として、残りの場所に正直者・嘘つきを条件を満たすように配置する組合せを考えることにする。

（ここまでがテクニックとして覚えておくべきなのだが、説明が分かりにくかったらごめん）

ここからも難しい。
先に正直者N個を置いておき、そこに嘘つきを挿入していくことを考える。
先頭には入れられないので、挿入先はN通りある。
ここで、嘘つきの集団をm個作ると考える。（←唐突ですが）
これをN通りの挿入先に入れていくことを考えると、同じところに集団を2ついれちゃうと、集団がマージされてm個にならないので、
N個からm個選んでいれることにする。
すると、白が隣接する箇所はN-m箇所になる。
しかも、嘘つきの集団をm個作ると考えると、黒が隣接する箇所はM-m箇所になる。
これは各集団の先頭m個を先に配置して、残りのM-mは配置するごとに黒の隣接箇所が1つ増えるためである。
何が言いたいかというと、嘘つきの集団の個数を固定すると、隣接が同じ箇所が分かるという嬉しさがある。

つらつら書いたが、解法に移る。
嘘つきの集団をm個として、mを[1,M]で全探索する。
mがN個より多くは作れないのと、隣接が同じ箇所は(N-m)+(M-m)となるので、これがK未満であるのもダメ。
すると、嘘つきの集団を入れる組み合わせはC(N,m)であり、嘘つきの集団の分け方はH(N,M-m)となる。
この積が嘘つきの集団がm個のときの組合せとなる。
これの総和を取って、×(N-1)!×M!をすると答え。

int N, M, K;
Comb<mint, 401010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;

    mint ans = 0;
    rep(m, 1, M + 1) {
        if (N < m) continue;

        int k = (N - m) + (M - m);
        if (k < K) continue;

        ans += com.nHk(m, M - m) * com.aCb(N, m);
    }

    ans *= com.fac[N - 1];
    ans *= com.fac[M];
    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

正直者大学 [yukicoder 1044]

解説