yukicoder No.950 行列累乗
https://yukicoder.me/problems/no/950
だいぶ手間取った。対角化は頭にちらついてはいたけど経験上、行列の成分が任意のときにこれをやると沼にはまるので避けた。結果として避けてよかったのかな。たぶんどっちを選ぶかは好みの問題な気がする。
行列でなく整数で $a^n=b \pmod{p}$ を求める問題であれば BSGS (baby step giant step) と呼ばれるアルゴリズムで解けます。今回の問題も
\begin{equation}
\begin{pmatrix}
a & 0 \\
0 & a
\end{pmatrix}^n
=
\begin{pmatrix}
b & 0 \\
0 & b
\end{pmatrix}
\end{equation}
という入力を考えれば整数のときの問題になりますから、整数のときより難しい問題だとわかります。そうなると BSGS が解法だろうと予想ができます。
一応 BSGS についても簡単に説明しておきます。BSGS というのは $a^n \equiv b \pmod{p}$ となる最小の負でない整数 $n$ を求めるアルゴリズムです。ここでは $a$, $b$ が整数のときを考えますが、行列でも同じようにできます。
BSGS はまず $a^0, a^1, a^2, a^3, \ldots, a^{9999}$ のなかに $b$ があるか調べ、なければ $a^{10000},a^{10001}, \ldots, a^{19999}$ のなかに $b$ があるか調べ、さらになければ $a^{20000},a^{20001},\ldots,a^{29999}$ を調べ、ということを繰り返すアルゴリズムです。この 10000 の部分はなんでもいいんですが、ここでは 10000 としておきます。このアルゴリズムを速く動かすことを考えましょう。$k$ 回目の反復では $a^{10000k},a^{10000k+1},\ldots, a^{10000k+9999}$ のなかに $b$ があるかを調べることになります。これは $a^0,a^1,a^2,\ldots,a^{9999}$ のなかに $b a^{-10000k}$ があるのか調べるのと同じことです。よって $\{a^0,a^1,a^2,\ldots,a^{9999}\}$ を集合のためのデータ構造を使って表しておいて、$b, b a^{-10000}, b a^{-20000}, \ldots$ がこのなかにあるか調べていけばよいということになります。
$A$ に逆行列がない場合は後回しにして $A$ の逆行列がある場合を考えます。つまり $\det A \ne 0$ です。このとき累乗 $E,A,A^2,A^3,\ldots$ をならべていくと、どこかでまた $E$ に戻ります。練習だとおもってこれも証明してみます。
まず二次正方行列は $p^4$ 通りしかありません。そのため $p^4+1$ 個の行列 $E, A, A^2, \ldots, A^{p^4}$ をもってくると鳩の巣原理よりかならず同じものがあります。それを $A^x$, $A^y$ とします。すると $A^x A^{y-x} = A^y = A^x$ になりますが、$A$ は逆行列をもつので左から $A^{-x}$ を掛けると $A^{y-x}=E$ となります。これで証明が終わりました。
はじめて $E$ に戻るときの指数を $ m $ としましょう。そうするとこたえは $1$ 以上 $ m $ 以下のどこかにあります。もし $ m $ がそんなに大きくなければ BSGS によって解くことができます。ちなみに BSGS は $O(\sqrt{m})$ で動きます。
さてそうなると $ m $ がどのくらいまで大きくなるかが気になります。さきほどの証明からわかるように $p^4$ よりは小さいです。もう少ししぼります。
ケーリーハミルトンの定理というのがあって、どんな二次正方行列も $A^2 - (a+d) A + (ad-bc) E = O$ を満たします。この定理を使うと $A^n=\square A + \square E$ と表せることがわかります。なぜかというと $A^n$ を $A^2 - (a+d) A + (ad-bc)E$ で割ると $A^n=\bigcirc (A^2 - (a+d) A + (ad-bc)E) + \square A + \square E$ となるからです。ただしここでいう割り算は行列の割り算ではなく多項式の割り算です。$\square$ には $p$ 通りの整数しか入りませんから、$A^n$ は $p^2$ 通りしかありえないことがわかります。
この見積もりが正しいのか、実際に $p=11$ や $p=13$ で確かめてみるといいでしょう。このくらいの周期をもつ行列がすぐに見つかります。そのため素朴に BSGS をするだけでは解けないこともわかります。
こういうときは何かしらの必要条件を考えて、探索範囲を狭めましょう。今回であれば行列式が使えそうです。$\det A^n = (\det A)^n = \det B$ は成り立たないといけないので、ここから $n$ がどのような数なのかがわかります。これを満たすような最小の正の整数 $n$ は BSGS で見つけられます。そうすると $(\det A)^k=1$ になる最小の正の整数 $k$ をつかって、 答えは $n, n+k, n+2k, \ldots$ のいずれかであることがわかります。
よって $A^{n+ sk} = B$ を満たす負でない整数 $s$ を見つける問題を解けばいいということになります。いま $A$ は逆行列をもつので $(A^k)^s=B A^{-n}$ としてよいです。これはもとの問題とほとんど同じ形をしていて、唯一違うのは $\det A^k = 1$ であることです。
$\det A=1$ であれば $\det A^2 = 1$ ですし、一般に $\det A^k=1$ です。そのため $E,A,A^2,A^3,\ldots$ はどれも行列式が 1 です。直感的には行列式のあたいが何でもよかったときと比べると周期が短くなりそうです。その直感を信じてプログラムで実験してみました。するとたしかに短くて $2p$ くらいで抑えられていることが分かりました。よって BSGS で解けます。
あとづけですが、周期が $2p$ で抑えられることを証明しましょう。$A^n=\square A + \square E$ と表せることはさきほどの通りです。ここから先では $A$ と $E$ を多項式のように扱います。つまり $aA + bE = cA + dE$ と $a=c$ かつ $b=d$ を同値として扱います。$X=\square A + \square E$ を固定します。このとき $X,2X,3X,\ldots,(p-1)X$ の行列式は $\det X, 2^2 \det X, 3^2 \det X, \ldots, (p-1)^2 \det X$ になります。つまりこの $p-1$ 個のなかで $X$ と同じ行列式をもつのは唯一 $(p-1)X$ だけです。
$\{X, 2X, 3X, \ldots, (p-1) X\}$ を $X$ の軌道と呼ぶことにします。軌道の大きさはかならず $p-1$ です。さきほどの議論から、$\det X=1$ のとき $X$ の軌道のなかに行列式が 1 になるものはちょうど 2 個あります。$A^n$ はいくつかの軌道に分解できます。軌道の大きさが $p-1$ なので、軌道の種類はたかだか $p^2 / (p-1)$ 通りしかありません。各軌道に行列式が 1 の行列が 2 つあるのなら、行列式が 1 の行列はたかだか $2p^2 / (p-1)$ 個であることがわかります。
$2p$ で抑えられることを示すつもりが、すこし違う結果になりましたが、計算量を考える上では問題ないでしょう。たぶん $\square A + \square E$ の形のものが $p^2$ 通りというのがもう少し抑えられます。ゼロ以外の多項式を考えているので $p^2-1$ 通り、これだと $2(p+1)$ で抑えられます。
$\det A = 0$ の場合ですが、自分はケーリーハミルトンの定理 $A^2=(a+d)A$ をつかって $A^n=(a+d)^{n-1} A$ として解きました。割りとこっちも思いつくのに時間がかかってます。こうすればただの整数のときの問題と同じです。
ケーリーハミルトンの定理、対角化と違って場合分けがでてこないから心が落ち着く。高校時代 $A^n$ を求めるときもケーリーハミルトンの定理でばかり求めていた気がする（遠い記憶。このみとか関係なしに対角化に誘導されるのが現実だけど）。
yukicoder No.940 ワープ ε=ε=ε=ε=ε=│;p>д＜│
https://yukicoder.me/problems/no/940
いくつかの組合せ問題は多項式によって解くことができます。これがどういうことか、簡単な例を取り上げて説明します。サイコロを二個振ったとき目の和が k となる場合の数を求める問題を考えましょう。いきなりですが次の式を考えます。
\[ (x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6) \]
これを展開すると
\[ x^2 + 2x^3 + 3x^4 + 4x^5 + 5 x^6 + 6 x^7 + 5 x^8 + 4 x^9 + 3x^{10} + 2x^{11} + x^{12} \]
になります。さて $x^k$ の係数は何になっているでしょうか。実はサイコロの目の和が k になる場合の数と一致しています。なぜかを詳しく説明しませんが、このように多項式の係数を見ることでいくつかの問題は解くことができます。
さて、このことを踏まえて今回の問題を多項式で表すと
\begin{align}
[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} \left( \frac{1}{(1-x)(1-y)(1-z)} - 1 \right)^k
\end{align}
を計算する問題になります。ここで $[x^X y^Y z^Z] f(x,y,z)$ は多項式 $f(x,y,z)$ の $x^X y^Y z^Z$ の係数を表します。この式の組合せ的意味を考えるには、$1/(1-x)=1+x+x^2+\cdots$ と置き換えた方がいいでしょう。なお $1/(1-x)$ は一般には多項式ではなく形式的冪級数と呼ばれますが、ここでは多項式と呼びます。
上の式を計算するにあたって次のことを大切にします。
\[ [x^a y^b z^c] \left( \frac{1}{(1-x)(1-y)(1-z)} \right) ^n = {}_n \mathrm{H}_a \cdot {}_n
\mathrm{H}_b \cdot {}_n \mathrm{H}_c \]
これは $[x^k]1/(1-x)^n = {}_n \mathrm{H}_k$ であることと、$[x^a y^b] f(x)g(y)=([x^a] f(x))([y^b] g(y))$ であることから導けます。前者は式の組合せ的意味から分かることです。後者は明らかです。もちろん分解しなくても組合せ的に直接導けます。
ここから先は $f=1/(1-x)(1-y)(1-z)$ とします。これにより計算対象は $[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k$ に変わります。この式は等比数列の和の形をしているので、数学 B で習う等比数列の和の公式を使いまとめられます。
\[ [x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k = [x^X y^Y z^Z] \frac{(f-1)^{X+Y+Z+1} - 1}{(f-1) - 1} \]
右辺の分子ですが、二項定理で展開すると $\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}$ の形になります。$X+Y+Z+1$ 次式を一次式 $f - 2$ で割るというのは数学 II で習う筆算を使えば $O(X+Y+Z)$ で計算できます。最後に係数を取り出せば良くて、
\[ [x^X y^Y z^Z] (\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}) = \square [x^X y^Y z^Z] 1 + \square [x^X y^Y z^Z] f + \square [x^X y^Y z^Z] f^2 + \cdots + \square [x^X y^Y z^Z] f^{X+Y+Z} \]
です。これで解けました。和を $X+Y+Z$ まで取りましたが、無限に広げることもできますし、そちらの方が自然かもしれません。ただし僕が知る限りでは計算が大変になります。
https://yukicoder.me/problems/no/940
Some combinatorial problems can be solved by polynomial. To explain this, I prepare a simple example: Find the number of patterns such that the sum of two numbers on two dices equals k. To solve this, we consider the following polynomial
\[ (x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6). \]
By expansion, we obtain
\[ x^2 + 2x^3 + 3x^4 + 4x^5 + 5 x^6 + 6 x^7 + 5 x^8 + 4 x^9 + 3x^{10} + 2x^{11} + x^{12}. \]
What is the coefficient of $x^k$? Actually, it is equal to the number of ways that the sum of dices equals k. Although I won't explain the reason, we can understand the power of polynomials.
Let's try to represent this problem as polynomial. Then, the answer becomes
\begin{align}
[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} \left( \frac{1}{(1-x)(1-y)(1-z)} - 1 \right)^k.
\end{align}
In this article, $[x^X y^Y z^Z] f(x,y,z)$ denotes the coefficient of $x^X y^Y z^Z$ in $f(x,y,z)$. To understand the meaning of this expression, $1/(1-x)=1+x+x^2+\cdots$ might be useful. By the way, $1/(1-x)$ is called not a polynomial but a formal power series in general, but I call both of them a polynomial.
Formal power series - Wikipedia
The following relation is useful in this problem.
\[ [x^a y^b z^c] \left( \frac{1}{(1-x)(1-y)(1-z)} \right) ^n = {}_n \mathrm{H}_a \cdot {}_n
\mathrm{H}_b \cdot {}_n \mathrm{H}_c \]
Since the proof of this relation is easy, so I don't explain it here. Let $f=1/(1-x)(1-y)(1-z)$. Then the answer is changed into $[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k$. This expression can be applied the sum of geometric sequence.
\[ [x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k = [x^X y^Y z^Z] \frac{(f-1)^{X+Y+Z+1} - 1}{(f-1) - 1} \]
We apply the binomial theorem to the numerator of the right hand side, then it becomes $\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}$. The division of a polynomial of degree $X+Y+Z+1$ and a polynomial of degree one can be computed in $O(X+Y+Z)$. Finally, we extract the coefficient from the result.
\[ [x^X y^Y z^Z] (\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}) = \square [x^X y^Y z^Z] 1 + \square [x^X y^Y z^Z] f + \square [x^X y^Y z^Z] f^2 + \cdots + \square [x^X y^Y z^Z] f^{X+Y+Z} \]
AtCoder Beginner Contest 144 F - Fork in the Road
https://atcoder.jp/contests/abc144/tasks/abc144_f
問題文には書いていないが制約に書いてある $s_i < t_i$ という条件から与えられるグラフは閉路を持たないことが分かる。この性質を使えば動的計画法によって期待値を求められる。それは以下の式によって得られる。
\begin{align}
E_i = \frac{1}{|N(i)|} \sum_{ j \in N(i)} (E_j + 1)
\end{align}
この式を計算するには $O(M)$ 掛かるため、ある辺を消してみて再び求めなおすと $O(M^2)$ 掛かってしまう。ここで諦めずに、ある辺を消してみて再び求めなおす処理をもっと速く行えないか考えてみよう。実は適切な前計算をしておくと辺一本あたり $O(1)$ で再計算できる。
辺 $(a,b)$ を消したときの期待値の変化量 $E_1' - E_1$ に着目する。実はこの変化量は $E_a' - E_a$ の変化量に比例する。これは上で書いた式の線形性に基づく。よってこの比例定数さえ知っていれば $E_1'-E_1$ は $E_a'-E_a$ から知ることができる。この比例定数を求める最も単純な方法は $E_a=1$ として上に書いた式を計算することだろう。計算し終えたときの $E_1$ が比例定数になっている。これを各頂点に対して行えば合わせて $O(NM)$ 掛かる。これでこの問題は解くことができるが比例定数を求める部分はもっと高速にできて $E_1=1$ として辺を逆向きに上記の計算をすればいい。よく考えると同じものを求めていることが分かるので、これで計算量 $O(M)$ になる。
このグラフが閉路を持たないことは次のように確かめられる。閉路が $v_1, v_2, \ldots, v_n, v_1$ があるならば矛盾することを示す。このときこのグラフの性質から $v_1 < v_2 < \cdots < v_n < v_1$ であり $v_1 < v_1$ となる。$v_1 < v_1$ かつ $v_1 \ge v_1$ より矛盾する。
この性質を持つような頂点の並べ方がトポロジカルソートであり、トポロジカルソートができるグラフは閉路を持たない、ということを知っていれば閉路を持たないことがすぐに分かるかもしれない。問題文に書いてくれていても良さそうな気がするが、引っかかったことで印象が強くなったと思えば悪くはなかったのかもしれない。
The problem statement doesn't say this graph is a DAG, but we can prove that this graph is a DAG. So we can solve this problem by using DP. The update formula is as follows.
\begin{align}
E_i = \frac{1}{|N(i)|} \sum_{ j \in N(i)} (E_j + 1)
\end{align}
We need O(M) time to calculate this formula, so straight forward solution takes O(M^2) time. We shouldn't give up at this point, this approach can be faster than $O(M)$ per edge. That is, O(1) algorithm exists.
Focus on the difference $E_1' - E_1$ when edge (a,b) is removed. Actually, this difference $E_1' - E_1$ is proportional to the difference $E_a' - E_a$. So if we already know the proportionality constant, we can easily obtain the new answer from $E_a' - E_a$. The easiest way to calculate the constant is to use the recurrence relation similar to the above formula. Needless to say, its requires $O(NM)$ in total, which is fast enough in this problem. However, we can speed up this solution more efficiently by doing similar DP on the reversed graph. I won't explain the details, but I believe that you can understand it by yourself. The true time complexity is only $O(M)$.
AtCoder Beginner Contest 144 E - Gluttony
https://atcoder.jp/contests/abc144/tasks/abc144_e
積の最大値を $x$ 以下にできるかどうかを二分探索する。$F_i$ は降順に並んでいるものと仮定する。このとき各 $F_i$ と対となる値は $\lfloor x/F_i \rfloor$ 以下になるはずである。
よって$A$ を自由に並び替えていいとき $\sum_{i=1}^{N} \max(0, A_i - \lfloor x/F_i \rfloor)$ としてありうる最小の値を求める問題が解ければいい。この最小の値が $K$ 以下ならば $x$ 以下にすることができる。結論をいうと、この値を最小にするには $A_i$ を昇順に並べるのがいい。そのことは以下のような図から分かる（操作後の大小関係が入れ替わるものはもっと値を小さくできるから大小関係が入れ替わる操作がいらない旨を示す図がこの次に入る）。
二分探索の各判定に $O(N)$ 掛かるので全体の計算量は $O(N \log (\max A_i \max F_i))$ である。
ずっと積の最大値じゃなくて和を最小化する問題だと思ってたんだけど、サンプル３を見つめていたら答えが１２になるはずがなくて勘違いに気がついた。
We can find the maximum product $x$ by using binary search. Suppose that $F_i$ are sorted in descending order. Then, the value correspond to $F_i$ is must be less than or equal to $\lfloor x/F_i \rfloor$.
Therefore, we only have to solve this problem: We can rearrange the array $A$ arbitrarily, then please find the minimum possible $\sum_{i=1}^{N} \max(0, A_i - \lfloor x/F_i \rfloor)$. If this value is smaller or equal to $K$, we can achieve $x$. Actually, if A is sorted in ascending order, this value becomes the minimum. That's why if the order of $A_i$ and $A_j$ are switched, we can construct more efficient solution by swapping the role of the both.
Each check in binary search can be done in $O(N)$, so the entire time complexity is $O(N \log \square)$.
AtCoder Beginner Contest 144 D - Water Bottle
https://atcoder.jp/contests/abc144/tasks/abc144_d
まず水をなみなみ入れておいてそれを傾けていったとき水の量がちょうど $X$ になる角度を求めればいい。どこまで傾ければいいかは二分探索によって求められる。二分探索するには傾けた角度に対してどのくらいの水が残るのかを知らなくてはならない。傾けた角度を $\theta$ としたときの水の量を求めよう。求め方は $\tan \theta < b/a$ を満たすかで変わる。これは水面がちょうど対角線の上に来るときの前後で求め方が変わるということである。条件を満たすなら以下の式になる。
条件を満たなさないなら以下の式になる。
以上でこの問題を解くことができた。式を見ればすぐわかるように逆正接関数で直にも解ける。
最初は二分探索書いたんだけど３ケースだけ落ちて戸惑ってた。誤差が厳しいのかと思って結局逆正接関数を使って解いたんだけど、誤差が厳しいわけがないし結局式が間違ってた。解説放送みたいに辺の長さが求まることに気づけば二分探索する気にはならないんだけど慣れでやってしまう。
図 https://github.com/pekempey/figure/tree/master/ABC144C_water_bottle
Binary Search. If we know the amount of the water remaining in the bottle when tilt theta, we can find the theta such that the amount becomes exactly X. Let's try to find the amount. First, we notice that there are two states, which switched by the condition tan theta < b/a. If this condition is satisfied, the amount can be expressed by the following formula.
If this condition isn't satisfied, the amount can be expressed by the following formula.
So we have solved this problem. By the way, where does this condition come from? Actually, tan theta = b/a means the water surface is just on the diagonal line.
