js2021 D問題 Nowhere P 数学問題を解説
js2021 D問題 Nowhere P を噛み砕いて解説します。
問題
2 以上の整数 P が与えられます。これはあなたの嫌いな数です。
整数の列 が以下の条件を満たすとき、この列を とても良い列と呼びます。
1 以上 N 以下のどの整数 i についても、 は P の倍数でない
各要素が 1 以上 P−1 以下であるような長さ N の整数列は全部で 個存在しますが、このうち とても良い列はいくつあるでしょうか?ただし、答えは非常に大きくなることがあるので、答えを で割った余りを出力してください。
解き方のイメージ
まずNやPの制約が最大でになってる時点で全探索はないなと考えます。
何かしら工夫が必要なのですが、「何かしらの工夫」を見つけるために、程よく小さめなNやPのケースを手を動かして考えてみます。
サンプルにある N = 3, P = 3で考えてみます。
N = 3なので、が3の倍数でないものがとても良い列になります。
を選ぶとすると、P = 3なので、1 か2のどちらかになります。
次に、を選ぶ時に、が3で割り切れないように選びます。
の時は、の時はです。
次にを選ぶときもが3で割り切れないように選びます。
の時はでです。
の時はでです。
Nの数を増やして、N = 4, P = 3だとしても、次のの選び方はそれぞれの分岐で1通りしかないことがわかります。
の時はでです。
の時はでです。
N = 3, P = 4 で考えます。
は特に制約はなく1〜3の間で好きに選べます。
はの時、4の倍数にならないように の2通りの中から選びます。
もちろんの時、4の倍数にならないようにの2通りから選びますし、
の時も4の倍数にならないようにの2通りから選びます。
次にの選び方を考えます。
の時、4の倍数にならないようにの2通りから選びます。
他の分岐も同じです。全部4の倍数にならないように3 - 1通りの2通りから選ぶことになります。
N = 3までの分岐の樹形図を描きました。
これまでのサンプルを踏まえてとても良い列の場合の数を考えると、
最初の選び方は通り、そのあとは通りを回繰り返します。
なので、答えはです。
で割った余りが求められています。
の計算は@drkenさんの以下の記事を参考にしました。
qiita.com
コードは以下のようになりました。
N, P = map(int, input().split()) MOD = 10**9 + 7 # a^n modを計算する def modpow(a: int, n: int, m: int): res = 1 while n > 0: if n & 1: res = res * a % m a = a * a % m n = n >> 1 return res ans = ((P - 1) % MOD) * modpow((P - 2), (N - 1), MOD) print(ans % MOD)