結果
問題 | No.1259 スイッチ |
ユーザー |
![]() |
提出日時 | 2020-10-16 23:04:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 1,851 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 91,776 KB |
最終ジャッジ日時 | 2024-07-20 23:35:32 |
合計ジャッジ時間 | 7,104 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
class Factorial(): def __init__(self, n): self.fct = [0] * (n + 1) self.inv = [0] * (n + 1) self.fct[0] = 1 self.inv[0] = 1 for i in range(n): self.fct[i + 1] = self.fct[i] * (i + 1) % MOD self.inv[n] = pow(self.fct[n], MOD - 2, MOD) for i in range(n)[::-1]: self.inv[i] = self.inv[i + 1] * (i + 1) % MOD def fact(self, m): return self.fct[m] def invf(self, m): return self.inv[m] def perm(self, m, k): if m < k: return 0 return self.fct[m] * self.inv[m - k] % MOD def invp(self, m, k): if m < k: return 0 return self.inv[m] * self.fct[m - k] % MOD def comb(self, m, k): if m < k: return 0 return self.fct[m] * self.inv[k] * self.inv[m - k] % MOD def invc(self, m, k): if m < k: return 0 return self.inv[m] * self.fct[k] * self.fct[m - k] % MOD def hcmb(self, m, k): if m + k == 0: return 1 return self.comb(m + k - 1, k) class Exponential(): def __init__(self, b, n): self.exp = [0] * (n + 1) self.inv = [0] * (n + 1) self.exp[0] = 1 self.inv[0] = 1 for i in range(n): self.exp[i + 1] = self.exp[i] * b % MOD self.inv[n] = pow(self.exp[n], MOD - 2, MOD) for i in range(n)[::-1]: self.inv[i] = self.inv[i + 1] * b % MOD def pow(self, k): if k >= 0: return self.exp[k] else: return self.inv[-k] MOD = 1000000007 N, K, M = map(int, input().split()) f = Factorial(N) e = Exponential(N, N) res = 0 for i in range(N): if K % (i + 1) == 0: res += f.perm(N - 1, i) * e.pow(N - 1 - i) res %= MOD if M == 1: print(res) else: print((e.pow(N) - res) * pow(N - 1, MOD - 2, MOD) % MOD)