37zigen

[37zigen @37zigen]

遷移係数列 aᵢ⁽ⁿ⁾ の生成関数が

Σᵢ₌₁∞ aᵢ⁽ⁿ⁾xⁱ = P⁽ⁿ⁾(x)/Q(x)

となる線形漸化式

cₙ = Σᵢ₌₁∞ aᵢ⁽ⁿ⁾cₙ₋ᵢ

の cₖ を求める問題は2種類の出題例がありそう？

・途中で P⁽ⁿ⁾ が更新される
・P/Q は固定だが、途中でいくつかの cₙ の値が外部から固定される

[37zigen @37zigen]

あとから始めた無限人に一瞬で抜かされるのが競プロ。それにAIも仲間入り。

[37zigen @37zigen]

これめっちゃ簡潔に書けるし、ライブラリで成敗できるし、嬉しい。メモリめっちゃギリギリになったけど…

[やまだ @yamada_null]

F 0になる値を後ろから特定してくと、コピー操作とsuffix破棄操作のみだから、永続平衡二分木でいける？

[37zigen @37zigen]

必要なのは min{x : ax + b <= c mod m} だった。
整備して通った。

[37zigen @37zigen]

A で min{(ax + b) mod m: 0 <= x <= n} のライブラリを持ち出して TLE した……

[37zigen @37zigen]

冷静になると二分探索要らなかった...

[37zigen @37zigen]

Eが一番簡単に感じた（ABC400点くらい）。

[37zigen @37zigen]

Dかなり難しく感じて、実験とかサンプルで適当に合わせてしまった。4つ目のサンプルの答えが大体N*Kでそこから、同じ数をほぼ全体に敷き詰めるんだろうと。

[37zigen @37zigen]

O(log n) の argmin{(ax + b) mod m: 0 <= x <= n} もライブラリ化しておくか.........

[37zigen @37zigen]

Fをライブラリでやっつける方法を教えて。

[37zigen @37zigen]

ABC466
Fが解けなくて緑perfの刑を喰らってそうで死

[37zigen @37zigen]

AWTFのAI全完を見て、自分のレート上げてもしょうがないし、ブログ復活させようかなという気にも…

[37zigen @37zigen]

@hotmanww その後は D, R 側をまた Half-GCD で再帰する。
つまり商列は

前半の再帰で得た商列 + 境界で正確に割った商 q + 後半の再帰で得た商列

を連結。

[37zigen @37zigen]

@hotmanww Half-GCD で 互除法の商列を列挙したいなら、返り値を「変換行列 M」だけにせず、「M を構成する商列 」も持てばいいと思います。

再帰で得た行列を full polynomial の (A, B) に作用させて (C, D) を得る。そこで半分の境界を越えていなければ、境界の 1 回だけは full polynomial で C=qD+R と割る

[37zigen @37zigen]

library checkerにresultantを提案
https://t.co/cTAmqAQG3h

[37zigen @37zigen]

Library Checkerにグレブナー基底を足したいと、うっすら思っているのだが、制約や高速な実装の仕方が悩みの種なんだよなぁ。競プロでは使わないが、いざ欲しいときに悩まされたので、界隈でコモディティ化して欲しいんだよね。

[37zigen @37zigen]

AWTFヒュ配信面白い
https://t.co/wp654OE2do

[37zigen @37zigen]

これ解説みたいに偶数番目をflipして一般化したかったんだけど、長さ奇数だと010 <-> 101 みたいに1が分裂してよく分かんなかったんだよな。

[37zigen @37zigen]

これ、言いかえ後の 0^k <-> 1^k で A を B にする最短手数が k≥3 でも O(N) で解けるよね。境界位置 p を q = (p mod k) として読み、不要な隣接する同じ q をスタックで消す。あとは境界位置のマッチング距離の和を取って k で割る。
https://t.co/VXdfypD3k4