No.492 IOI数列

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 131
作問者 :

square1001 / テスター :

e869120

3 ProblemId : 1283 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2017-03-10 22:17:16

あるとき, lttさんは, あるコンテストで101位を取ってギリギリ賞金を逃がしてしまいました。

しかし, いつもポジティブなlttさんは, 次のように考えました。

「『101』・・・これはIOIを表している。これはIOIに行けるような実力を持っているということだ！」

そこで, 彼は次のような「IOI数列」という数列を定義し, 自信を高めようとしました。

IOI数列は, $1, 101, 10101, 1010101, 101010101, 10101010101, \dots$ と続く数列です。

彼は, この数列が $a_{1} = 1, a_{i} = 100 a_{i - 1} + 1$ となっていることに気付きました。

しかし, これを速く解く方法を彼は知らなかったので, 友達であるあなたに手伝ってもらうことにしました。

整数 $N$ が与えられます。そのとき, IOI数の第N項を $1000000007$ で割った余りと $101010101010101010101$ で割った余りを求めなさい。

$N$

1行目に整数 $N (1 ≦ N ≦ 10^{18})$ が与えられる。

1行目に $a_{N}$ mod $1000000007$ を出力しなさい。

2行目に $a_{N}$ mod $101010101010101010101$ を出力しなさい。

最後に改行を忘れないこと。

10101
10101

$a_{3} = 10101$ です。

101003031
1010101010101

$a_{7} = 1010101010101$ であり, $a_{7}$ mod $1000000007 = 101003031$ となります。

963727330
101

$a_{101}$ mod $101010101010101010101 = 101$ となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。