任意の多項式は任意の中心 c のまわりの冪級数として容易に表すことができる。 ただし係数のほとんどは 0 になる。 冪級数は定義により無限個の項を持つからである。例えば、多項式 f(x) = x 2 + 2x + 3 は中心 c = 0 のまわりの冪級数として = + + + + + ⋯と書くことができ、また中心 c = 1 のまわりでは は冪級数とは考えない(ローラン級数ではあるが)。同様に、 一応、シリーズとしてまとめたく…。 第1回:数え上げとの対応付け → ■ 前回は、いろいろな数え上げの問題が、多項式(形式的べき級数)の問題に変換されることを確認しました。しかしこれだけでは、通常の dp の考え方をそのまま翻訳しただけです。まぁデータの持ち方を多項式にしただけですからね。 多項式に言い換えられる時点で、 dp の遷移の立式はできているわけです。一方で、時にはそのままの立式に基づくと計算 … 問題文 → ■自分の提出 → ■公式解説pdf → ■ x a | AtCoder 第一回 日本最強プログラマー学生選手権 -予選- → ■ 問題F – Candy Retribution → ■ 自分の提出 → ■ 私はこの問題は、コンテスト中には解ききれなかった(解き方は分かったものの、残り時間がなくて実装を終えられなかった)のですが、公式解説にはない、形式的べき級数による考察をとったので、考察の要点などを書き残しておこうと思います。また、この問題をきっかけとして、形式的べき級数の数え上げへの基本的 … 【問題】出典:EDPC-M リンク:■ $a_1,\ldots, a_N$ が与えられる。自然数 $0\leqq x_i\leqq a_i$ を選んで、$x_1+\cdots + x_N = K$ となるようにする方法の総数を求めよ。※ $N\leqq 100$, $a_i\leqq K\leqq 10^5$. ) ) ) 既に埋まってる数値部分はそれっぽく遷移。それ以外は、$10^k$ の位のところに多項式 $F_k = \sum_{n=0}^{9}x^{10^kn}$ を当てます。, これらの積を計算すればよいですが、指数の $\pmod{13}$ での値だけが問題です。よって、$x^{13}=1$ というルールを追加した上で多項式の積を計算していくことになります(詳しい人向け:多項式環の剰余環 $K[X]/(X^{13}-1)$ における積)。, $x^5$ などをかけるのは係数の位置をずらすだけです。さらに、$F_n = F_{n+6}$ を利用すると、次が本質ということが分かります:, $F_0^{a_0}F_1^{a_1}\cdots F_5^{a_5}$ を($x^{13} = 1$ のもとで)計算せよ。$\sum a_i = N \leqq 10^5$。, 愚直計算で、多項式の積を $N$ 回程度計算することになります。(この方法でも解けて、コンテスト想定解と同等)。しかし、大きな $a$ に対して $F^a$ の計算する方法といえば、$\Theta(\log(a))$ の回数の乗算で計算できることはよく知られた通りかと思います。, 結局、この問題の主要部は $N$ について $\Theta(\log N)$ 時間で計算できます(’?’ の位置を検出するところに $\Theta(N)$ 要るので結局全体では $\Theta(N)$ 解法)。, 本問題で計算量が落ちることに言及していた人は少なかったような気がします。繰り返し二乗法の適用にあたり、多項式の積の, が本質的に使われています。が、多項式に対するこれらの性質は、新しいアルゴリズム知識として学ばずとも、空気のように使える方が多いのではないでしょうか?上の解説でも、交換法則や結合法則を利用した場所を明示していません。, などの形になると思いますが、多項式と違って高校数学までで馴染みが薄い人の方が多いと思います。また、この手の高速化は「行列累乗」というくくりで定跡化され語られているのをよく見かけますが、多項式で解釈できる場合にはそのようにしておいた方が、計算量も有利になります($D$ 次多項式の乗除の愚直計算は $\Theta(D^2)$ で、$D$ 次正方行列の乗除の愚直計算は $\Theta(D^3)$ です)。, 例をたくさん挙げようとすると、収集がつかなくなってきそうでしたので、この辺でいったん終わります。, ときには、その構造を代数的な変形として導出できるだろうということになります。(強めの主張ですが、例外はほぼ存在しないと思います。「問題を多項式の形に表すこと」の時点で困難な問題はたくさんあります。), 今回取り上げたのは、どの問題も、多項式という考え方がなくとも解けるものばかりです。またひとつひとつの問題自体は、組合せ的解釈などによる方が簡単に、あるいは自然に立式できていると感じる方も多いと思います。ただ、一見すると全く異なる数え上げテクニックが、文字式を簡単にするという共通の考え方から同じように導かれているところは注目に値すると思います。, ・ABC 159 F – Knapsack for All Segments ・JSC2019-qual F-Candy Retribution・KUPC2019 K-One or All. 2 {\displaystyle f^{(0)}(c)=f(c)} 2 数学において、(一変数の)冪級数(べききゅうすう、英: power series)あるいは整級数(せいきゅうすう、仏: série entière)とは, の形の無限級数である。ここで an は n 番目の項の係数を表し、c は定数である。この級数は通常ある知られた関数のテイラー級数として生じる。, 多くの状況において c(級数の中心 (center))は 0 である。例えばマクローリン級数を考えるときがそうである。そのような場合には、冪級数は簡単な形, これらの冪級数は主に解析学において現れるが、組合せ論においても(形式的冪級数の一種である母関数として)現れ、電気工学においても(Z変換の名の下で)現れる。実数のよく知られた十進表記(英語版)もまた冪級数の例と見ることができる。係数は整数であり、引数 x は 1/10 に固定されている。数論における p 進数の概念もまた冪級数の概念と密接に関係している。, 冪級数の取り扱いには大きく分けて二つある。四則演算などの代数的性質のみに着目する形式冪級数と、関数などの解析的性質に着目する収束冪級数である。, 数列 (an)n∈N が有限列であるとき、つまり適当な自然数 m があって、n>mなら必ず an = 0 が成り立つような列であるとき、これを係数列とすることによって得られる形式冪級数, 多項式に対してはその係数列の有限性から係数が 0 にならない添字の最大値 max{n∈N | an ≠ 0} として次数 deg(f) を考えることができたが、冪級数に対して同じことを考えるとほとんど全部の冪級数の次数は無限大であり、したがって、形式冪級数は形の上では多項式の次数を無限大に飛ばした類似物であると見ることができる一方で、形式冪級数に対して次数を考えてもほとんど何の役にも立たないということになる。形式冪級数に対して“多項式における次数”のような役回りを演じるのは、係数が 0 にならない添字の最小値 min{n∈N | an ≠ 0} である。多項式と形式冪級数との関係は有理数と実数(の無限小数展開)および p-進数(の p-進展開)との関係の類似であり、実際に冪級数を有限体上で考えれば、これら類似性は大域体とその局所化である局所体との関係として一般的に取り扱われる。, 収束冪級数は形式冪級数にその収束域を考え合わせたもので、収束冪級数はその収束域上で関数を定める。特に複素解析において解析関数を取り扱う際に重要な役割を演じる。, 数列の持つ性質を母関数によって調べる組合せ論的な手法では、得られる冪級数が収束することが、冪級数に操作を施して得られた数列の性質をすべて肯定することになるため、収束性の確認は重要である。にもかかわらず、数列にとっては母関数が“何らかの意味で”収束する点を(中心以外に)持ちさえすればよいので、母関数の収束性にそれほど注意が払われることもない。, 任意の多項式は任意の中心 c のまわりの冪級数として容易に表すことができる。ただし係数のほとんどは 0 になる。冪級数は定義により無限個の項を持つからである。例えば、多項式 f(x) = x2 + 2x + 3 は中心 c = 0 のまわりの冪級数として, と書け、他の任意の中心 c のまわりの冪級数としても書ける[1]。冪級数を「無限次の多項式」のようなものとみなすことができる。冪級数は多項式ではないが。, は、|x| < 1 に対して有効であるが、冪級数の最も重要な例の1つであり、任意の実数 x に対して有効な指数関数の公式, 負冪は冪級数においては許されていない。例えば、 c = 事実(今回のテーマ) どんな関数も,べき級数(無限次の多項式関数)として表すことができる. x | $F_{i} = 1 + x + x^2 + \cdots + x^{a_i}$ とする。$[x^K] F_1F_2\cdots F_N$ を計算せよ。, 一般に、$d$ 次多項式の積は愚直計算で $\Theta(d^2)$ の計算量が必要になって、$K$ 次式の積を $N$ 回行うのは本問の制約では無理です(FFTによる任意mod乗算 $N$ 回は…ややきついくらい?)。, $F_i$ に対して何らかの構造を見出して、計算量を落としましょう。因数分解のときと同様にして、多項式に対するよりいい感じの表示を探していきます。, 等比数列の和から、$F_i = \frac{1-x^{a_{i}+1}}{1-x}$ と式変形できます。割り算ですが、疎な(係数がほとんど $0$ であるような)多項式 2 つで表せており、より上手く $F_i$ を扱えそうです。さらに、\[F_i = \frac{1}{1-x}\cdot (1-x^{a_i+1})\] と表してみましょう。「$F_i$ を因数分解した」と考えても、まぁ良いと思います。(多項式の範囲だけで物事を見ているとこの変形はできなくて、考察の範囲を形式的べき級数に広げて考える利点が現れています。), 結局のところ、ある多項式 $P$ に $F_{i}$ をかける操作は、次のように分解することができます。, 一般に、$P = \sum_{n=0}^{\infty}p_nx^n$, $\frac{P}{1-x} = Q = \sum_{n=0}^{\infty}q_nx^n$ としてみましょう。このとき、$(1-x)Q = P$ ですから、$[x^n]$ 部分を比べて $n\geqq 1$ に対して $q_n – q_{n-1} = p_n$ が成り立つことが分かります。したがって $q_n$ は漸化式 $q_n = q_{n-1} + p_n$ と初項 $q_0 = p_0$ で計算していくことができて、1 件あたり $\Theta(1)$、$d$ 次以下の部分を $\Theta(d)$ で計算できます。, ※ 一般に、疎な多項式による乗法・除法は高速に計算できます。※ 結局、$\{q_n\}$ は $\{p_n\}$ の累積和です。 $\frac{1}{1-x} = 1 + x + x^2 + \cdots$ に基づく説明も可能で、その方が分かりやすいかもしれません。「疎な式への分解」を発見すれば自然に計算量が落ちるという思考法を強調するため、上記の説明をとりました。 分母が $2$ 次式など状況が変わっても対応できます。, 操作2はどうでしょう?これは簡単で、係数の列を $(a_i+1)$ 個ずらして引くだけです。結局、$F_i$ による dp 遷移は、, なお、形式的べき級数の積は交換法則を満たすため、この 2 つの手順を逆順に行っても同じ計算結果が得られることが分かります。$N$ 個の積 $f_1\cdots f_N$ を計算するにあたって、$\prod_i(1-x^{a_i})$ を計算したあとで $N$ 回累積和をとるような計算手順も可能であることが分かります。お好みの順序で実装しましょう。, もちろん多項式を使う必要はないです。ふつうにやれば、$\mathrm{dp}[n] + \mathrm{dp} [n-1] + \cdots + \mathrm{dp} [n-a_i]$ といった形で dp 遷移式に現れます。区間和を計算する常套手段といえば累積和を補助的に利用する。これは多項式を知らずとも典型ですね。, ちなみにこの問題、 $N = 10^5$ とかでも解けそうですね…この辺の話もそのうち書きます。, 【問題】出典:ARC028-D リンク:■ $a_1,\ldots, a_N$ が与えられる。自然数 $0\leqq x_i\leqq a_i$ を選んで、$x_1+\cdots + x_N = K$ となるようにする方法の総数を求めよ。いや、これは少し簡単過ぎるので、ちょっとした注文も追加する…「$x_k = c_k$ のもとで数え上げよ」というクエリ $Q$ 個に答えよ。※ $N\leqq 2000, 0\leqq a_i\leqq M\leqq 2000, Q\leqq 500000$, 前問題の変形バージョン。クエリが $Q$ 個ありますが、たくさんありすぎるので結局すべての $(k, c_k)$ に対して計算することが想定されています。, $F_{i} = 1 + x + x^2 + \cdots + x^{a_i}$ とおく。各 $i$ に対して、$\prod_{j\neq i}F_j$ の $M$ 次以下の部分を計算せよ。, 全体集合から 1 元抜いたところで何か集計する場合には、左右からの累積を計算するのが典型テクニックです(例:■)。しかし、左右からの積をマージするところに $\Theta(M^2)$ かかるので、それを $N$ 回やるのはつらめです(※ それでもFFTで高速化すればACが得られます)。もう少し良い構造を見つけたいところです。, という方法も、ごく自然に考えられます。$F_i$ による除法はどうなるでしょうか?, $F_i = \frac{1-x^{a_i+1}}{1-x}$ でした。よって形式的べき級数環において、\[ \frac{F}{F_i} = F\cdot (1-x)\cdot \frac{1}{1-x^{a_i+1}}\] と書くことができます。$F$ から $\frac{F}{F_i}$ を得る操作は、次の通りです:, どちらも疎な多項式による乗算・除算なので、$\Theta(M)$ で計算できて目的が達成されます。より具体的な係数に対する操作としては、, 累積和による dp 更新・戻す dp といった個別の思えるテクニックが、文字式で見ると単純な掛け算・割り算で同時に説明されています。立式で混乱する要素も少ないでしょう。(ほんと?).

.

Âクセル Âラフ Ɩ字 ƞ, Excel Ãウスホイール Âクロールできない, Ãジャー ż肩 Âョート, Âュース ȩめ合わせ ƿ安 ɀ料無料, Lisa Ǵ蓮華 Tシャツ, Âゾンアメックス Suicaチャージ Ãイント, ɯの ǔ姜 Dž ɻ金比率, ɝ椒肉絲 Ãシピ Áけのこなし, Ãラシ Âイズ Ǩ類, Ƨ目 Ãング Ãランド, Ƿ Âインドブレーカー Âーデ, ȱ腐 Áけるだけ Ãイエット, 7月16日 Ȋ火 Ƿ持寺, šり絵コンテスト ŭ供 2020, ň譲マンション Âンクリート壁 ǩ, Mbrからgpt Âローン Easeus, Mojangアカウント Microsoftアカウント ɀ携, Ɲ芝レグザ ƕ障 ɟ声, Áさ Âチ ō葉雄大, ɛ乳食 Ãレーク Ť望, Âッズ Ãレーナー ǔの子 Ůい, Ãソコン2台 Ãニター2台 ň替 Hdmi, ɉ道会社 Ƿ合職 Ź収, Ãマハ Ãリヂストン Ãッテリー互換, Ãウシカ Ãラモデル Âイ, Áさ Âチ ō葉雄大, Ǥ会人 Ł差値 Ãスト, Âルテン Ãリークッキー Ãンキング, ȋ会話 ŏ付 Ãイト ŭ生,