Many Shifts Easy [yukicoder No.823] - はまやんはまやんはまやん

前提知識

二項係数mod素数

解説

こういう系に初めて取り掛かる人はどこから手をつけていいか分からないと思うが、
まずは弱そうな条件を探してみる。
見ると、入力がN≦10^5となっている。
しかも、得点の計算方法がマスの番号の総和となっているので、マスの番号で全探索できそうだ。
　
これはよくある方針で、問題では
「ある数列に対して各マスでの得点を計算」して総和
としているが、今回は各マスで得られる得点は一定なので、そうではなくて、
「各マスでの得点が得られる数列の組み合わせを計算」して総和
という方針で計算していく。
　
あるマスiで得点が得られる、つまり、駒が残るのは以下のような数列のときである。

iが含まれない
iもi+1も含まれるが、iがi+1より前にある

　
よって、このどちらかを満たす数列を数え上げて、組み合わせ×iの総和を取れば答えになる。
　
iが含まれない
i以外のN-1個からK個選んで数列を作るだけなので、組み合わせはP(N-1, K)
　
iもi+1も含まれるが、iがi+1より前にある
iとi+1以外のN-2個からK-2個選んで数列を作って、そこにi,i+1を差し込む感じで数える。
iとi+1以外のN-2個からK-2個選んで数列を作る組み合わせはP(N-2, K-2)
iとi+1を差し込む組み合わせはC(K, 2)
よって、P(N-2, K-2)×C(K,2)通り

これで組み合わせが求まった。
各iについて、組み合わせの個数は変わらないので、前計算しておこう。
　
1つ注意があり、i=Nの場合はN+1が存在しないので、「iが含まれない」組み合わせだけで計算する。

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

	mint c = 0;
	c += com.aPb(N - 1, K);
	c += com.aPb(N - 2, K - 2) * com.aCb(K, 2);
	
	mint ans = 0;
	rep(i, 1, N) ans += mint(i) * c;
	ans += mint(N) * com.aPb(N - 1, K);
	cout << ans << endl;
}