結果
問題 | No.492 IOI数列 |
ユーザー |
![]() |
提出日時 | 2017-03-11 00:18:00 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 101 ms / 1,000 ms |
コード長 | 790 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 7,680 KB |
実行使用メモリ | 12,416 KB |
最終ジャッジ日時 | 2024-06-24 09:15:05 |
合計ジャッジ時間 | 3,202 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
コンパイルメッセージ
Syntax OK
ソースコード
def expt(a, n, p) res = 1 while n > 0 do res = res * a % p if n % 2 == 1 a = a * a % p n >>= 1 end return res end p = 1000000007 q = 101010101010101010101 d = Array.new(60) d2 = Array.new(60) d[0] = 1 for i in 1..59 do d[i] = d[i-1] * (expt(10, 1 << i, p) + 1) % p end d2[0] = 1 for i in 1..59 do d2[i] = d2[i-1] * (expt(10, 1 << i, q) + 1) % q end n = gets.chomp.to_i x = 0 m = n-1 idx = 0 while m > 0 do if m % 2 == 1 then x = (x * expt(10, 1 << (idx+1), p) % p + d[idx]) % p end m >>= 1 idx += 1 end x = (x + expt(100, n-1, p)) % p print "#{x}\n" x = 0 m = n-1 idx = 0 while m > 0 do if m % 2 == 1 then x = (x * expt(10, 1 << (idx+1), q) % q + d2[idx]) % q end m >>= 1 idx += 1 end x = (x + expt(100, n-1, q)) % q print "#{x}\n"