問題概要 原文 → C: 高橋君、24歳 - AtCoder Regular Contest 009 | AtCoder 長さの順列を並び替えたとき、 (1-indexed)となる要素が個になる組み合わせは何通りか。1,777,777,777 (素数) で割った余りを出力せよ。 解説 まず、となる要素をどこにするかを決めます。これは個の中から個を選ぶ組み合わせであるため、と同値です。1,777,777,777を法として計算するため、この計算をするためには逆元の知識が必要ですが、それは他のサイトに委ねます。階乗の計算すると思うけど再帰で書いたらダメですよ、もれなくスタックオーバーフローします。 問題なのは、となるような長さkの順列が何通り作れるかを求めることです。漸化式を求めれば解けそうな雰囲気はしますが、どんな漸化式になるでしょうか。 最初に、長さの場合を考えましょう。 長さ1で元と異なる