ABC006-B - トリボナッチ数列 を解く(3)

ABC006-B - トリボナッチ数列 を解く(2) の続き

MLE 対策をしてコードを修正するも今度は TLE になってしまった

…この問題ムズくね？

競プロ初心者が挑戦したら挫折するレベルだろ

せめて n の上限が 10^6 じゃなくて 10^5 だったら前回のコードで通ったろうに

何か他に手がかりは …ん？

 

＞ トリボナッチ数列の第 n 項、an を 10007 で割った余りを 1 行で出力してください。

 

そういえば、この 10007 ってなんだろう？

もしかしてこの数字に関係した公式でもあるのか

 

（検索中…）

 

なぜか 1000000007 で割った余りについて解説するサイトをよく見るな…

どれどれ…

 

どうやら 10007 も 1000000007 も素数らしい

 

そんでもって足し算の場合は、最終結果を素数で割った余りとする場合は

計算途中で素数の余りをとっても構わないとのことだ

 

提出したコード

# a1=0, a2=0, a3=1
a=0
b=0
c=1

# 入力
n=int(input())

# n=1,2,3 の場合
if n==1:
  print(a)
  exit()
elif n==2:
  print(b)
  exit()
elif n==3:
  print(c)
  exit()

x=0
for i in range(3,n):
  x=a+b+c

  # 10007 で余りをとる
  x%=10007

  # 次の計算の準備
  a=b
  b=c
  c=x

# n番目の項を10007で割った余りを出力
print(x%10007)

 

提出結果は… AC ！

 

大変だったけど、なんとか解けてよかった