E. Product Oriented Recurrence

Quiz

https://codeforces.com/contest/1182/problem/E

f:id:peroon:20190723134300p:plain

Note

f:id:peroon:20190613015237j:plain

Editorial

https://codeforces.com/blog/entry/67614

天才かよ!?と思った点

  • cxを分解(分配)することでcx fxの形にできる
  • 三項の積になるが、g(x, p)を導入して三項の和にする
  • するとトリボナッチとなり、行列累乗の二分自乗法が使えてO(logN)で第N項が求まる
  • あとはcxの逆元をフェルマーの小定理から求めればいい

追記:2019/07/23 何もわかっていませんでした

  • イデアだけ見て分かった気になっていた
  • ちゃんと解いた
  • writing....