[問題案] Factorization of Polynomials(factorization_of_polynomials)

yosupo06 commented 5 years ago

F_p 上の多項式の因数分解

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

yosupo06 commented 5 years ago

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

hos-lyric commented 5 years ago

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

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

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

yosupo06 commented 5 years ago

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

yosupo06 commented 5 years ago

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

yosupo06 commented 5 years ago

問題概要

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 commented 5 years ago

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

yosupo06 commented 5 years ago

monicじゃないと出力が嫌な感じになると思っていて、monicにしたいです
- (順序を無視して)一意に定めるなら、定数項として最高次を出力？じゃあ最高次が1の時は？ウーン　みたいな
N次じゃなくて、f(x) = \sum_{i = 0}^{N - 1} a_i x^i ですね
可変, 固定modは実はどうするかあんまり決めていない(というか、難しすぎるて決められない)んですが、(mod sqrtのように)計算量にmodのサイズが出てくるなら可変という気分になってきました(convolutionを固定から可変に置き換えるだけで動くとかなら固定で良いんじゃないかという気分なんですが、そうではなさそう？)
同じ因子はまとめなくていいんじゃないかなって気分ですそっちのほうが出力チェッカも楽そうですし
出力の順番は任意で良いんじゃないかなぁと思っています　辞書順でsortもmodintに大小決めることになって変ですし

yosupo06 commented 5 years ago

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

yosupo06 commented 5 years ago

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

hos-lyric commented 5 years ago

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

(順序を無視して)一意に定めるなら、定数項として最高次を出力？じゃあ最高次が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 commented 5 years ago

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

hos-lyric commented 5 years ago

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

yosupo06 commented 5 years ago

😣

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

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

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

hos-lyric commented 2 years ago

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

yosupo06 / library-checker-problems

[問題案] Factorization of Polynomials(factorization_of_polynomials) #94