等比数列に単項式が掛かっているものの和を計算するyosupo judgeの問題

スナネコです。yosupo judgeにある \sum_{i=0}^{n-1}r^i i^d を解きました。
https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial

yosupo judge の github を見ると参考文献が載ってます。
https://github.com/yosupo06/library-checker-problems/issues/98

そういうわけで、この記事は Min_25 さんによる以下の記事を私の理解で書き直したものです。
ひとによってはオリジナルの方がわかりやすいかもしれません。
https://web.archive.org/web/20170622095007/http://min-25.hatenablog.com/entry/2015/04/24/031413


話の流れはこうです。
・数列 a_n=\sum_{i=0}^{n-1}r^i i^d を漸化式で表す
・係数行列の固有多項式を求める
・固有多項式で割ったあまりを explicit な式で表す

ステップ1. 漸化式を出す

本題に入る前に、単項式 n^d の値を n に関する漸化式で求めるにはどうすればよいか考えてみましょう。
全ての i\leq d についての n^i を持てばできますね。具体的には、(n+1)^dn^i と二項係数を使って書けることから言えます。例えば

\pmatrix{
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 2 & 1 & 0\\
1 & 3 & 3 & 1\\
}
\pmatrix{
1\\
n\\
n^2\\
n^3\\
}=
\pmatrix{
1\\
(n+1)\\
(n+1)^2\\
(n+1)^3\\
}
となります。二項係数を並べたこの下三角行列のことを下三角パスカル行列というそうです。n\times n の下三角パスカル行列をwikipediaでは L_n と表しているので、ここでもそう書くことにします。

本題に戻ります。ここまでわかれば元の問題を漸化式で書くのは簡単です。

\pmatrix{
1r & 0r & 0r & 0r & 0\\
1r & 1r & 0r & 0r & 0\\
1r & 2r & 1r & 0r & 0\\
1r & 3r & 3r & 1r & 0\\
0 & 0 & 0 & 1 & 1
}
\pmatrix{
r^n\\
r^n n\\
r^n n^2\\
r^n n^3\\
\sum_{i=0}^{n-1} r^i i^3
}=
\pmatrix{
r^{n+1}\\
r^{n+1} (n+1)\\
r^{n+1} (n+1)^2\\
r^{n+1} (n+1)^3\\
\sum_{i=0}^{(n+1)-1} r^i i^3
}
こうですね。左上の (d+1)\times(d+1) の小行列を L_{d+1} とまとめて書くことにして
M:=\pmatrix{
 & 0\\
rL_{d+1} & \vdots\\
 & 0\\
0\ 0\ \ldots \ 0\ 1 & 1
}
A_n:=\pmatrix{
r^n\\
r^n n\\
\vdots\\
r^n n^d\\
\sum_{i=0}^{n-1} r^i i^d
}
とします。求めたいものは A_n の最後の成分であり、A_n=M^nA_0A_0=(1,0,0,\ldots,0) です。
ここまでくれば、線形漸化式を持つ数列の第 n 項を求めるのと同じようにできそうな気がしてきましたね。

ステップ2. 係数行列の固有多項式を求める

なぜ固有多項式を求めたいのか一応説明しておきましょうか。一般に、行列 A の固有多項式 p_Ap_A(A)=O を満たします。このことから、f(x)=(x^n \bmod p(x)) とすると、M^n=f(M) となります。*1
そうすると、小さい次数の項しか残らないので、いろいろ話が簡単になるわけです。

それでは本題に戻ります。さっき求めた係数行列 M の固有多項式 p を求めましょう。
M は下三角行列で、対角成分は rd+1 個、11 個なので、p(x)=(x-r)^{d+1}(x-1) です。……はい、これだけです。

詳しくは省略しますが、ここまでわかれば、線形漸化式のときと同じように高速きたまさ法で O(d\log d\log n) で元の問題を解くことができます。

ステップ3. 固有多項式で割ったあまりを求める

きたまさ法を使った解法では f(x) を求めるために O(d\log d\log n) の時間がかかりますが、実はこの問題の場合は f(x) の係数を直接計算することができるので、よりよい計算量で解くことができます。
ここから先はひたすら計算が続きます。ちゃんとついてきてくださいね。

f の形から、定数 c と、d 次以下の多項式 g を用いて、f(x)=c(x-r)^{d+1}+g(x) と書けます。この cg を頑張って求めます。

g について

この g は要するに (f\bmod (x-r)^{d+1})=(x^n\bmod (x-r)^{d+1}) です。n< d+1 なら自明です。そうでないときは g(x+r)=( (x+r)^n\bmod x^{d+1})=\sum_{k=0}^{d}\binom{n}{k}r^{n-k}x^k になるので、あとは x をずらすだけですね。
\begin{eqnarray}
g(x)&=&\sum_{k=0}^{d}\binom{n}{k}r^{n-k}(x-r)^k\\
&=&\sum_{k=0}^{d}\binom{n}{k}r^{n-k}\sum_{i=0}^{k}\binom{k}{i}(-r)^{k-i}x^i\\
&=&\sum_{i=0}^{d}r^{n-i}x^i(-1)^i\sum_{k=i}^{d}\binom{n}{k}\binom{k}{i}(-1)^k
\end{eqnarray}
k に関する和が残ってしまいました。二項係数なので階乗に書き下して変形してもよいですが、組合せ的な言い換えをした方がわかりやすいことも多いです。今回、二項係数の積の部分は「n 個から k 個選び、さらに選んだ k 個から i 個選ぶ方法の数」だと思えます。これは「n 個から i 個選び、さらに選ばなかった n-i 個から k-i 個選ぶ方法の数」と等しいので、こういうふうに変形できますね。
\begin{eqnarray}
& &\sum_{k=i}^{d}\binom{n}{k}\binom{k}{i}(-1)^k\\
&=&\sum_{k=i}^{d}\binom{n}{i}\binom{n-i}{k-i}(-1)^k\\
&=&\binom{n}{i}(-1)^i\sum_{k=0}^{d-i}\binom{n-i}{k}(-1)^k\\
&=&\binom{n}{i}(-1)^i\binom{n-i-1}{d-i}(-1)^{d-i}
\end{eqnarray}
最後の等号は、\binom{x}{y}=\binom{x-1}{y-1}+\binom{x-1}{y} を使って \binom{n-1}{*} を全部 \binom{n-1-i}{*} に置き換えて計算するとわかります。そういうわけで、g は具体的に次のような形で書けました。
g(x)=\sum_{i=0}^{d}r^{n-i}(-1)^{d-i}\binom{n}{i}\binom{n-i-1}{d-i}x^i

c について

すでに g が求まっているので、適当な値を x に代入して、恒等式 f(x)=c(x-r)^{d+1}+g(x)c に関する 1 次方程式だと思って解くだけですが、適当な x に対して f(x) を求めるのはそんなに簡単ではないので、簡単に計算できる x を探す必要があります。どんな x なら簡単に求められるでしょうか。実は、(x-1)|p(x)f(x)=(x^n\bmod p(x)) をあわせると f(1)=(f(x)\bmod (x-1))=(x^n \bmod (x-1))=1 になるので、x=1 を選べばよいです。このとき、1=c(1-r)^{d+1}+g(1) を得ます。r\neq 1 ならこれで話は終わりです。r=1 のときは c の係数が 0 になってしまうので、これではうまくいきません。r=1 のとき、元の問題は単なる単項式の和なので、最初から場合分けをして取り除いておいてもいいんですが、せっかくなのでいまやったのと同じような方法で求められないか考えてみましょう。

r=1 のときに c を求める

f(x)=c(x-r)^{d+1}+g(x) という恒等式を思い出すと、gd 次以下だったことから、cfx^{d+1} 次の係数と等しくなります。r=1 のとき p(x)=(x-1)^{d+2} なので、「f(x)=(x^n \mod (x-1)^{d+2})d+1 次の係数を求めよ」という問題になりますが、上で g を求めるときにやったのと全く同じ議論で \binom{n}{d+1} になることがすぐわかります。

ステップ4. a_n を求める

これも線形漸化式の第 n 項を求めるときと全く同じですが、一応説明しておきましょう。
求めたいものは A_n=f(M)A_0 の最後の成分でした。f(x)=\sum_{i=0}^{d+1}c_ix^i とおくと、A_n=\sum_{i=0}^{d+1}c_iM^iA_0=\sum_{i=0}^{d+1}c_iA_i となります。つまり a_n=\sum_{i=0}^{d+1}c_ia_i なので、a_0,\ldots,a_{d+1} を予め愚直に求めておけば計算できます。

計算量解析

計算する必要があるものは a_0,\ldots,a_{d+1}f(x)=c(x-r)^{d+1}+g(x)=\sum_{i=0}^{d+1}c_ix^i です。
計算量は O(d \log {\rm MOD}+\log n) に見えますが、線形篩・線形逆元列挙・N乗数の高速列挙・二項係数の差分計算など、細かい工夫をたくさんすると O(d+d \log {\rm MOD}/\log d+\log n) になります。

私の実装例はこれです。線形篩ではなく普通の篩を使っているので、計算量は O(d\log\log d+d \log {\rm MOD}/\log d+\log n) になっています。
https://old.yosupo.jp/submission/81322


ラグランジュ補間でも解けるという話を聞いたのですが、私はまだわかっていません。誰か教えてくれますか?

*1:二項演算 mod は、剰余環に送るのではなく、割り算して余りを求める演算子とします

AGC051C『Flipper』

サーバルだよ! AGC051C『Flipper』の解説をするよ!

コンテスト中の考察

なんだかライツアウトっぽいね。
ライツアウトと同じようなことをすれば解けそう。
ライツアウトをmod2での連立方程式だと思って解く方法と同じプログラムを書いて、6×6や7×7で実験をすると、ライツアウトの「解の存在条件」の式と同じようにして、今回の問題の操作での不変条件の式が出てくるんだけど、その式をぐ~~~っと睨むと、次の2つが不変量になってることがわかるよ。
・各列の黒マスの個数の偶奇
・各行の、「mod3で0の列と1の列にある黒マスの個数の合計の偶奇」「mod3で0の列と2の列にある黒マスの個数の合計の偶奇」
あとはこの不変量を崩さない条件も下で黒マスの個数を最小化すればいいね!

f:id:kyopro_friends:20210104185956p:plain

行の条件をもうちょっと丁寧に見ておこうかな。各行にあるmod3で0,1,2の列にある黒マスの個数を(x,y,z)で表すことにすると、「mod3で0の列と1の列の黒マスの個数の合計の偶奇」「mod3で0の列と2の列……」が、
・(偶,偶)なら(0,0,0),(1,1,1),……
・(奇,偶)なら(0,1,0),(1,0,1),……
・(偶,奇)なら(0,0,1),(1,1,0),……
・(奇,奇)なら(1,0,0),(0,1,1),……
になるよ。偶奇だけしか見てないから、例えば(偶,奇)なら(4,2,1)とかももちろん作れるね。
ということは、最初の盤面で上の4通りになってる行がそれぞれP,Q,R,S個、列について「黒マスの個数が奇数であるようなmod3で0,1,2の列の個数」をX,Y,Zとすると問題は次のように読み替えられるよ!

問題:
P,Q,R,S,X,Y,Zが与えられたとき、次の条件を満たすような(x,y,z)について、x+y+zの最小値を求めよ。
・(x,y,z)は、(0,0,0)か(1,1,1)をあわせてP個、(1,0,0)か(0,1,1)をあわせてQ個、(0,1,0)か(1,0,1)をあわせてR個、(0,0,1)か(1,1,0)をあわせてS個、(0,0,2),(2,0,0),(0,0,2)を好きな個数、合計したものである
・x≧X かつ y≧Y かつ z≧Z
・x≡X かつ y≡Y かつ z≡Z mod2

(Q,R,S)が考えられる最小なんだけど、x≧Xの条件とかを満たしてないときにどうするかを考えないといけなくて、(0,0,2)はタダで使えるけど+2だから、(1,0,0)を(0,1,1)に変える+1を優先するのが良くて、でも個数制限があって…………
というところで2時間悩んで本番中に結局解けなかったよ…………

コンテスト後の考察

まずQ=R=S=0のときはX+Y+Zが答えになることが少し考えるとわかるね。そうじゃないときを考えよう。
(Q,R,S)をベースに改善することを考えるんだけど、例えば(1,0,0)→(0,1,1)と(0,1,0)→(1,0,1)を両方やるのは(1,1,0)→(1,1,2)だから、(0,0,2)をタダでもらうのと同じになるね。
ということは結局、どの種類を何個変換するかを全探索すればOK!
Submission #19200670 - AtCoder Grand Contest 051 (Good Bye rng_58 Day 2)
うーん、数学でうまく最適解を求めるんじゃなくて、全探索すればよかったんだね……。前半パートがめちゃくちゃ数学だったから、すっかり数学頭になってたよ…………。




前半の考察の数学的な説明

あれ、今日は全部サーバルさんが解説すると思ってたんですが、数学パートは私がやるんですか? いいですけど。
そういうわけで解説のスナネコです。
不変量を求めるときに登場した方程式が何をやっていたのかをちょっと説明します。

盤面をN×Nとして、各マスが白か黒かを0,1に対応させることで、盤面は\mathbb{F}_2のN^2次元ベクトルとみなすことが出来ます。
また、1回の操作も、操作によって変化するマスを1とするベクトルとみなすことで、盤面に対する操作は、ベクトルの足し算だと思うことが出来ます。
f:id:kyopro_friends:20210104180037p:plain
よって「操作に関する不変量を求めよ」という問題は、「(H-1)(W-2)種類の操作に対応するベクトルで張られる、\mathbb{F}_2^{N^2}の部分空間Vの元が満たすべき条件式を求めよ」になります。
(H-1)(W-2)個の操作が独立であることは少し考えるとわかります(ある元を、その元以外の線形結合で作ろうとしても、右下から貪欲に決めるしかなくうまくいかないことがわかります)。
なので、操作が張る部分空間の次元は(H-1)(W-2)であり、この部分空間の元が満たす条件式の個数はHW-(H-1)(W-2)=2H+W-2になります。
あとはサーバルさんがやったように実験をすると不変量っぽいものが見つかりますが、一応これが不変量であることを確認しておきましょう。
・列に関する条件の方は明らかですね。どの操作でも、各列のちょうど2マスが変化するので、黒マスの偶奇は変わりません。
・行に関する条件の方は、mod3で行を塗り分けるとわかります。どの操作でも、赤と青、赤と緑がちょうど2マス含まれるので、赤+青、赤+緑の部分にある黒マスの偶奇は変わりません。
f:id:kyopro_friends:20210104184325p:plain
列に関する条件式がW個、行に関する条件式が2H個で合わせて2H+W個あるように見えますが、列に関する条件のうち、右端2つの列の分は、他の条件から導くことができるので実質2H+W-2個です。
あとはこれらの条件が独立であることを確認すればよいですが、面倒なので省略します。

AtCoder practice contest B問題 Interactive Sorting

スナネコです。
AtCoderpractice contestのB問題を解いたので解説を書きます。

問題ページにあるコード例を読むとわかりますが、この問題は「Q回以下の比較で、長さNの数列をソートせよ」と読み替えられます。

(N,Q)=(26,1000)のとき

コード例に書いてあるとおり、バブルソートなど、O(N^2)のソートアルゴリズムを実装すると通ります。
(26,100)のアルゴリズムでも当然解けるので、(26,100)が解けるなら、(26,1000)のためのコードを書く必要はありません。

(N,Q)=(26,100)のとき

最悪計算量がO(N\log N)のソートアルゴリズムを書く必要があり、定数倍にも気をつける必要があります。
マージソートをすると、99回の比較でソートできることが証明できます。

(N,Q)=(5,7)のとき

本題です。
7回の質問で得られる情報7bit128パターンから、ありえる数列の並び5!=120通りを特定する必要があります。
この厳しすぎる条件から、毎回の質問は返答がほぼ半々に分かれるようにするしかないことがわかるので、何を質問すればいいか選択肢が絞れます。

1回目

(A,B)を質問し、A<Bと返ってきたとしてよいです。残りの可能性は60通りです。

2回目

質問として(A,C) か (C,D)のどちらかが考えられます。
(例えば(B,C)は数列全体を反転すれば(A,C)と同じですし、(C,E)はDとEを入れ替えれば(C,D)と同じです)
(A,C)を聞いてA<Cと返ってきた場合、ありえる数列が40通り残るので、残りの5回で判別できません。
なので(C,D)を聞きます。C<Dとしてよいです。残りの可能性は30通りです。

3回目

質問として(A,C)、(A,D)、(A,E)の3通りが考えられます。
(A,D)を聞いてA<Dと返ってきた場合、ありえる数列が25通り残るので、残り4回で判別できません。
(A,E)を聞いてA<Eと返ってきた場合、ありえる数列が20通り残るので、残り4回で判別できません。
なので(A,C)を聞きます。A<Cとしてよいです。残りの可能性は15通りです。

4回目

現時点でA<C<D、A<Bがわかっています。ABCDの並び順はABCD,ACBD,ACDBのどれかで、さらにEがどこに入るかで3×5の15通りの可能性があります。
意味のある質問と、最悪ケースを考えると
A>E 12通り
B>C 10通り
B<D 10通り
B>E 9通り
C<E 8通り
D>E 11通り
となるので、(C,E)と質問するしかないことがわかります。

4回目でC<Eになったとき

A<C<(D,E) かつ A<Bがわかっています。DEの順序を確定するのに1回、Bの位置4通りを確定するのに2回の計3回で特定できます。

4回目でC>Eになったとき

意味のある質問と、最悪ケースを考えると
A<E 4通り
B>C 4通り
B>D 5通り
となるので、(A,E) か (B,C)を質問すればよいです。どちらでもあと2回の質問で特定できますが、(B,C)の方があとが簡単です

5回目でB<Cになったとき

A<B<C<D、E<Cがわかっているので、Eがどこに入るか3通りを2回で確定できます

5回目でB>Cになったとき

(A,E)<C<(B,D) となるので、AE,BDの順序をそれぞれ2回で特定すれば良いです。


以上でこの問題が解けました。
最後の何回かの質問の部分の場合分けがちょっと大変ですが、他に選択肢はないので、頑張って場合分けを実装するしかなさそうです。

ABC174C Extra

スナネコです。twitterで出した問題について解説します。

問題その1:
高橋君は K の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて K の倍数が登場するのは何項目ですか?
存在しない場合は代わりに -1 を出力してください。

制約:
 K\leq 10^{12}

解説:
K が 7 の倍数のときK'=K/7、そうでないとき K'=K とします。
次のように同値変形できます

  • 77...77 (n桁)が K の倍数
  • 11...11 (n桁)が K' の倍数
  • 99...99 (n桁)が 9K' の倍数
  • 10^n = 1 \bmod 9K'

よって、最後の式を満たす最小の n を求めれば良いです。

解法1:離散対数問題
この問題は離散対数問題そのものなので、Baby-Step Giant-Stepなどを用いることで、O(\sqrt{K} \log K) で解くことができます。

解法2:乗法群における位数
明らかに、K が2の倍数か5の倍数のときは答えが-1になることがわかります。
そうでないとき、オイラーの定理から、10^{\phi(9K')}=1 \mod 9K'が成り立ちます。
なので、10^n = 1 \bmod 9K' を満たす最小の n は、\phi(9K') の約数となることがわかります。
(もしそうでなければ、 n'=gcd(n,\phi(9K'))として、より小さい答えが作れるので矛盾します)
\phi(9K')を求め、素因数分解し、約数を全探索することで、O(\sqrt{K})で解くことができます。

128bit整数がないとちょっと計算が大変ですね。





問題その2:
高橋君は K の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて K の倍数が登場するのは何項目ですか?
1\leq K\leq N の全ての K について求めてください。
存在しない場合は代わりに -1 を出力してください。

制約:
 N\leq 10^{6}

解説:

10^n=1 \bmod M を満たす最小の nf(M) と書くことにします。
もし、a,b が互いに素なら、10^n=1 \bmod ab を満たす最小の n は、中国剰余定理から lcm(f(a),f(b)) になることがわかります。
よって、素数べきに対する答えが求めることができれば、それらを組み合わせて一般の場合に答えることができます。
最初に 9N 以下の数の最小素因子テーブルを作っておき、素因数分解O(\log N) で出来るようにしておきます。(osa_k法というやつですね)
素数 p に対しての答えは、問題その1で説明した方法によって、O(\text{p-1の約数の個数}\times \log N) で求めることが出来ます。
証明は省略しますが、f(p^e)f(p^{e-1})p f(p^{e-1})になります。どちらになるかは実際に計算することで、O(\log N) で確かめられます。
(証明は「f(p^e)\neq f(p^{e-1}) \Longrightarrow f(p^e) = p f(p^{e-1})」を二項定理を使って示します。ちなみに、f(p^e)=f(p^{e-1})になるのは、e=2 のときの 3, 487, 56598313 の3通りしか知られていないようです(A045616))
これらをうまく組み合わせると、全体で O(N\log N) で解くことができます。

埋め込みで解けてしまうのと、O(N\sqrt{N})との区別が難しいのとで、実際のコンテストに出すのは無理ですね。

Nim product

スナネコです。
yosupo judgeのNim productを解きました。
問題

よくわからないですが、Nimber product、Nimber multiplicationみたいな呼び方もあるみたいです。なんて読むんですかこれ?

私に読める言葉で書かれたものが見つからなくて困ったので、丁寧めに解説を書きました。
pdfで4ページくらいなので読んでみてください。
https://drive.google.com/file/d/16g1tfSHUU4NXNTDgaD8FSA1WB4FtJCyV/

無限和を計算するyosupo judgeの問題

スナネコです。yosupo judgeにある \sum_{i=0}^{\infty}r^i i^d を解きました。
問題

d=0の時はただの等比数列の和です。
d=1の時を計算する問題もときどき見ますね。例えば「1の目が出るまでサイコロを振るときの回数の期待値は?」とかです。
…………冗談です。まさかこの問題でそんな計算しませんよね?

さて、dが大きなときでもやることはd=0,1の時と同じで、rを掛けて差を取っていきます。
例えばd=4のときは

\begin{eqnarray}
S &=& 1*r &+& 16*r^2 &+& 81*r^3 &+& 256*r^4 &+& 625*r^5 &+& \cdots \\
rS &=& \     &\ & 1*r^2 &+& 16*r^3 &+& 81*r^4 &+& 256*r^5 &+& \cdots \\
(1-r)S &= & 1*r &+& 15*r^2 &+& 65*r^3 &+& 175*r^4 &+& 369*r^5 &+& \cdots \\
r(1-r)S &=&\ &\  & 1*r^2 &+& 15*r^3 &+& 65*r^4 &+& 175*r^5 &+& \cdots \\
(1-r)^2 S &= & 1*r &+& 14*r^2 &+& 50*r^3 &+& 110*r^4 &+& 194*r^5 &+& \cdots \\
r(1-r)^2 S &=&\ &\  & 1*r^2 &+& 14*r^3 &+& 50*r^4 &+& 110*r^5 &+& \cdots \\
(1-r)^3 S &= & 1*r &+& 13*r^2 &+& 36*r^3 &+& 60*r^4 &+& 84*r^5 &+& \cdots \\
r(1-r)^3 S &=&\ &\  & 1*r^2 &+& 13*r^3 &+& 36*r^4 &+& 60*r^5 &+& \cdots \\
(1-r)^4 S &= & 1*r &+& 12*r^2 &+& 23*r^3 &+& 24*r^4 &+& 24*r^5 &+& \cdots \\
r(1-r)^4 S &=&\ &\  & 1*r^2 &+& 12*r^3 &+& 23*r^4 &+& 24*r^5 &+& \cdots \\
(1-r)^5 S &= & 1*r &+& 11*r^2 &+& 11*r^3 &+& 1*r^4
\end{eqnarray}
という感じですね。
なんだか見たことのない数が残りました。こういうときはOEISです。
1,11,11,1 - OEIS
Eulerian Numberというらしいです。d=5の場合も計算すると一致したので多分あってるでしょう。
wikipediaを見てみます。
Eulerian number - Wikipedia
wikipediaに合わせて、Eulerian NumberをA(n,m)と表すことにしましょう。
スナネコは英語は読めませんが、数式を見れば大体の雰囲気はわかりますね。
A(n,m)を表す式は書いてありますが、nを固定したときに全部のmを高速に求める方法は書いてなさそうです。

このEulerian Numberを使って計算できればいいんですけど、うまくいきますかね。ちゃんと式に書いてみましょう。
\displaystyle{
\sum_{m=0}^{d-1}A(d,m)r^{m+1}\\
=\sum_{m=0}^{d-1}\sum_{k=0}^{m} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\
}
愚直に計算するとO(d^2)です。困りました。
正解者の提出をちらっと見てみると、こういう式で計算してました。
\displaystyle{
\sum_{i=0}^d  (-r)^{d-i} \binom{d+1}{i+1} \sum_{j=0}^{i} r^j j^d
}
スナネコの考えてる式と似たような感じなので、今の方針であってそうです。
二項係数の部分と、(…)^dの部分で変数を分離して、独立に累積和っぽく計算する工夫は面白いですね。これが使えないか試してみます。m+1-kをxと変数変換してみます。
\displaystyle{
\sum_{m=0}^{d-1}\sum_{k=0}^{m} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\
=\sum_{k=0}^{d-1}\sum_{m=k}^{d-1} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\
=\sum_{k=0}^{d-1}\sum_{x=1}^{d-k} (-1)^k\binom{d+1}{k}x^d r^{x+k}\\
=\sum_{k=0}^{d-1} (-1)^k\binom{d+1}{k} \sum_{x=1}^{d-k}x^d r^{x+k}\\
=\sum_{k=0}^{d-1} (-r)^k\binom{d+1}{k} \sum_{x=1}^{d-k}r^x x^d\\
}
うまくできましたね。これで、xのシグマについてはkが大きい方から累積和のように計算していくことができるので、高速に計算できるようになりました。
この計算式の通りにやっても全体でO(d\log mod)ですが、逆元テーブルの線形構築や細かい計算を配列にメモしておくことでいくらか定数倍高速化が効きます。

これでAC……ではありません。d=0の時はそもそも最初の\sum_{m=0}^{d-1}A(d,m)r^{m+1}の時点で空和になって0になってしまいます。仕方がないのでこれだけ場合分けです。

ACは取れましたが、途中で紹介した他の正解者の計算式では場合分けをしてないみたいです。こっちも導出してみましょう。
最後の数式でd-kをyに変数変換します。
\displaystyle{
\sum_{k=0}^{d-1} (-r)^k\binom{d+1}{k} \sum_{x=1}^{d-k}r^x x^d\\
=\sum_{y=1}^{d} (-r)^{d-y}\binom{d+1}{d-y} \sum_{x=1}^{y}r^x x^d\\
=\sum_{y=1}^{d} (-r)^{d-y}\binom{d+1}{y+1} \sum_{x=1}^{y}r^x x^d\\
}
和を取る範囲が違いますね。ここが0から始まっているとd=0のときにも場合分けをしなくて済むようです。
wikipediaをよく見てみると、A(0,0)=1、n>0のときA(n,n)=0、と書いてありました。ということはそもそも一番最初の式の時点でm=dまで和を取ってよくて、そうすると整合性がありそうですね。
\displaystyle{
\sum_{m=0}^{d}A(d,m)r^{m+1}\\
=\sum_{m=0}^{d}\sum_{k=0}^{m} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\
=\sum_{k=0}^{d} (-r)^k\binom{d+1}{k} \sum_{x=0}^{d-k}r^x x^d\\
=\sum_{y=0}^{d} (-r)^{d-y}\binom{d+1}{y+1} \sum_{x=0}^{y}r^x x^d\\
}
確かに同じ式が求まりました。

精進について

サーバルだよ!
競プロの精進について書くよ。
精進の仕方や、精進に対する考え方はいろいろあるから、あくまで私の意見だと思って読んでね。

■3行でまとめて

・復習が大事。解けた問題も解けなかった問題も、解説やいろんな子の実装を見てみる
・典型を身につけるのは大事。ABCは解説ACでもいいので解く
・写経はできればしない。一回自分で書いてみてから他の子の実装をパクる

■モチベーションについて

レートがついて他の子と競う以上、やっぱりレートが下がると面白くないよね……。
私も最近は下がってこそないけど全然上がらなくて面白くないよ……。
f:id:kyopro_friends:20200202161207p:plain

モチベーションが低いときに無理してコンテストに出ても成績は悪くなりがちだから、そういう気分のときはしばらくコンテストに出ないというのももちろんありだよ。
だけど、私には「コンテストに出て悔しい思いをして、解けなかった問題をちゃんと復習する」って方が合ってるから、できるだけコンテストには出るようにしてるんだ。

■パフォーマンスを上げるには

パフォーマンスを上げるためには「簡単な問題をよりはやく解く」「より難しい問題を(どうにか)解く」の少なくともどっちかが必要だよ。
本当に目指すべきは「難しい問題を解く」の方で、「簡単な問題をはやく解く」っていうのは、難しい問題を考える時間を残すために必要なことだね。
・自分の色未満のdiffの問題を、考察も実装も悩まずに解けるようにする
・自分の色のdiffの問題を解けるようにする
あたりを目標にするといいんじゃないかな。
私たちが青の頃は400~600点を埋めてたよ。このあたりの難易度を一通り埋めれば、典型にはだいたい触れられると思う。
水未満なら300点400点あたりかな?



■考察パートについて

一番大事なのは「自分がコンテスト中に解けなかった1問」を解けるようになることだよ。
私が復習するときは
・知識が足りなかったなら覚えて、それを使う関連する問題を(あれば)解く
・知識は足りていたけど、考察できなかったときは、「どうすれば思いつけたか」を考える
ってことを考えながらしてるね。
解説ACについては、ABCの問題で1時間考えて解けないなら、知識が足りない可能性が高いから解説を読んだ方がいいと思うよ。
典型を知らない状態から自分で発明できれば、多分もう忘れることはないと思うけど、時間は有限だからね……。
逆にAGCは、C問題あたりまでなら特別難しい知識はいらない問題が多いから、じっくり考えるのもあり。私はこっちもすぐ解説を読んじゃうけど…………。

■どうすれば思いつくのか?

「どうすれば思いつくか?」にはいろんなアプローチって、例えば私がよく考えるのはこの2つ。
・簡単な部分問題から考える(もし与えられるグラフが木なら解ける。一般のグラフの場合は……)
・愚直解法を考える(O(N^3)のDPはすぐわかるけどN≦2000だから間に合わない。無駄な計算を省くには……)
他にも、計算機科学?に詳しい子は
・解けない問題を考える(もしこの条件がないとNP完全になって解けないから、この条件をうまく使う必要があって……)
みたいな考え方をすることもあるらしいけど、私にはよくわかんないや。

■実装パートについて

AtCoderに限れば実装が大変な問題はそんなに出ないから、「実装が大変そう」って思ったらもっと解法が整理できないか考えてみるのが1つの手だね。
もちろん難しい実装をきっちりやりきる力も大事だけど、難しい実装に手をつけてバグらせたら大変だし、それが嘘解法だった日には目もあてられないよ…………。
私はコンテスト中には「これよりいい解法が思い付けそうになくて、今の難しい実装をバグらせずに通せる自信がある」ってときだけ、難しい実装に手をつけることにしてる……つもりなんだけどな~。

■解説ACと写経について

写経って言葉をみんながどういう意味で使ってるのかよく知らないけど、私は「誰かのコードを横に見ながらコードを書くこと」はほとんどしないよ。
誰かの実装を見たり解説を読んだら、自分の中でよく噛み砕いて、なにをやっているのかを理解してから何も見ずに1から書くのが好きだからね。
解法・アルゴリズムを本当に理解したなら、(少なくとも、理解したはずのその瞬間には)なにも見ずに書けるようになるはずだと私は思ってるし、特に、できれば「なんでこれでうまくいくのか」まで分かるようにしておくと、応用の幅がぐっと広がるはず!
もちろん自分で書ききったあとは、もう1回他の子のコードを参考にしながら、書き直すのは大事だよ。細かい実装のテクニックを身につけるのにも役立つし、「自分はこう書いてしまったけど、こうするともっとスッキリ書ける」っていうのを確かめられる絶好の機会だもんね。(実装のテクニックだと「めぐる式二分探索」が一番有名なのかな?)
他にもACがはやい方から何人かのコードは、びっくりするくらい簡潔なことが多いから参考になるよ! 簡潔すぎてよくわからないこともあるけど……。

■復習について

解けなかった問題だけじゃなくて、解けた問題も復習するのは大事だよ。自分が解いたのよりもっと簡単な方法があったりするかもしれないし。
公式の解説pdfだけじゃなくていろんな解説記事を読むのがいいよ。
ずっと前、ガイドさんが私に勉強の仕方を教えてくれたときに、「よくわからないことがあったら、10種類くらい解説を読んでみると、そのうち1つくらいは自分にとって分かりやすいものがあるはず」って教えてくれたんだ。
10種類……はさすがにできてないかもしれないけど、1つや2つの解説を読んでわけがわからなくても諦めないようにはなれたはず。



そんな感じで私は精進してるよ!
なんだか精進の話とはちょっとズレてる気もするけど、参考になるかな?