[問題案] Factorization of Polynomials(factorization_of_polynomials)

[yosupo06]

F_p 上の多項式の因数分解

Originally posted by @hos-lyric in https://github.com/yosupo06/library-checker-problems/issues/3#issuecomment-530911792

[yosupo06]

まず想定計算量が全くわからないん　助けて〜

[hos-lyric]

参考文献 https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields

O(次数^3 + 次数^2 log p) 回 F_p の元の加減乗をします．除はたぶんそんなしてない． 定数倍は，わたしも気になります 多項式の乗算除算を速くやると 1 つ落ちるかも…… (小さい p も本質であることもお伝え)

C++ の想定解を実装するのはやぶさかではありません (しかしデータを作るのに既約性判定が要るという話があり，それは似たようなことをするとできる)

[yosupo06]

やってくれるととても嬉しいです -> 想定解

[yosupo06]

• 問題ID: factorization_of_polynomials
• 問題名: Factorization of Polynomials

[yosupo06]

• 問題概要

N次の多項式f(x)が与えられます因数分解をしてください

• 入力

N
a_0 a_1 ... a_{N - 1}

• 出力

M
K_0 b_0 b_1 ... b_{K_0 - 1}
K_1 b_0 b_1 ... b_{K_1 - 1}
:
K_{M - 1} b_0 b_1 ... b_{K_{M - 1} - 1}

ただしMは因数の個数、b_0, ... が因数の多項式

• 制約

想定解の速度を眺めながら a_{N - 1} == 1?

• 検討事項

modをどうするか(固定？可変？)

[hos-lyric]

• monic はわたしのライブラリだと仮定しちゃってたけどどっちでも
  • でも出力は monic に限定したいよね
• N 次なら a_0, ..., a_N という話がある
  • 最高次を省くかどうかは好みだと思うけど 1 と書くことにするのがいいかなぁ
• mod は可変がいいな (p = 2 かどうかで場合分けするため)
• 同じ因子をまとめるかどうか (どっちでもいい，上に貼った方法でやると勝手にまとまる)
• 出力の順番はどうするか (整数 factorize と違って標準的な順序があるわけでもないしなんでもいいのかな)

[yosupo06]

• monicじゃないと出力が嫌な感じになると思っていて、monicにしたいです

  • (順序を無視して)一意に定めるなら、定数項として最高次を出力？じゃあ最高次が1の時は？ウーン　みたいな

• N次じゃなくて、f(x) = \sum_{i = 0}^{N - 1} a_i x^i ですね

• 可変, 固定modは実はどうするかあんまり決めていない(というか、難しすぎるて決められない)んですが、(mod sqrtのように)計算量にmodのサイズが出てくるなら可変という気分になってきました(convolutionを固定から可変に置き換えるだけで動くとかなら固定で良いんじゃないかという気分なんですが、そうではなさそう？)

• 同じ因子はまとめなくていいんじゃないかなって気分です そっちのほうが出力チェッカも楽そうですし

• 出力の順番は任意で良いんじゃないかなぁと思っています　辞書順でsortもmodintに大小決めることになって変ですし

[yosupo06]

• https://github.com/yosupo06/library-checker-problems/blob/master/docs/guildline.md ここを参考に想定解と(できればチェッカ)を作っていただけると助かります　その他はどちらでも大丈夫です
• フォルダがない状態から僕以外がやるの初めての試みなんで、わからないことがあったら聞いてください(多分ドキュメントとかも僕が気づいてないだけで不明瞭な部分があると思います…)
• Assignは衝突を避けるためにつけることにしました
• 当然ながら全く急ぐ必要はないんですが、やめたくなったらいつでも言ってください

[yosupo06]

というかmod sqrtを含むんだから可変ですね(気づき)

[hos-lyric]

まったりやります (でもテストケース追加してくれる人とかも募集しています)

(順序を無視して)一意に定めるなら、定数項として最高次を出力？じゃあ最高次が1の時は？ウーン　みたいな

定数 × monic × ... × monic (定数は必ず 1 個出力する) はそんなに嫌な形ではないと思うけど，まあ煩雑になるだけなのですべてを monic にしようかな，mod inv は他でチェックということで

N次じゃなくて、f(x) = \sum_{i = 0}^{N - 1} a_i x^i ですね

次数を書いて N a_0 ... a_N のほうが綺麗だと思うな (宗教戦争) (monic しかないので特に)

可変, 固定modは実はどうするかあんまり決めていない(というか、難しすぎるて決められない)んですが、(mod sqrtのように)計算量にmodのサイズが出てくるなら可変という気分になってきました(convolutionを固定から可変に置き換えるだけで動くとかなら固定で良いんじゃないかという気分なんですが、そうではなさそう？)

そうではないですね，具体的には，

• p = 2 の場合分け，それ以外にも，p が次数より小さいと突然微分が消えるなどの不都合がありえてちょっと気を遣います (問題としては定義されているので正しく扱いたい)
• なにかの多項式を法としてなにかの多項式を p 乗するシーンがあります (計算量に log p がでてくる元)
  • そんなことを言っていたら mod inv をする問題すべて関わって来ないか？ということに気づいてしまった，むずかしいね

convolution をまじめにやってどのくらい速くなるかは要検証…… (f(x) mod g(x) を速くやるやつとか持ってないんだよね，困っちゃったな，Gifted のライブラリを使って想定解を書くとかをやっちゃおっかな) あとどうでもいいけど，ほんとうに mod sqrt を含むかはちょっとわからず

同じ因子はまとめなくていいんじゃないかなって気分です そっちのほうが出力チェッカも楽そうですし 出力の順番は任意で良いんじゃないかなぁと思っています　辞書順でsortもmodintに大小決めることになって変ですし

OK

[yosupo06]

x^2 - aの因数分解はmod sqrtを含むアルゴリズムが必要じゃないですか？

[hos-lyric]

わたしがばかでした，罵ってください

[yosupo06]

😣

次数を書いて N a_0 ... a_N のほうが綺麗だと思うな (宗教戦争) (monic しかないので特に)

とりあえずmonicじゃない場合はN = 配列長 でもういくつかの問題を準備してしまっています。で、その上でmonicの場合をどちらにするかなんですが、どっちでも理由付けが出来ることに気づいてしまい (monicとか関係なくN = 配列長を貫く / Nをある種の自由度として捉える)、困りました

という思考を経て、結論としては、どっちでも大丈夫ということになりました(なので、hosさんのいうN a_0 ... a_Nの方で進めましょう)

[hos-lyric]

これ放置してしまっていてすみません……． 手元の環境の都合ですぐ (1 か月以内とか) にはできなさそうです． やってくださる方いらしたら歓迎です．