$$\begin{bmatrix} \sum_{i=0}^{N+1} F_i^2 \\F_{N+2}F_{N+1}\\ F_{N+2}^2 \\ F_{N+1}^2 \end{bmatrix}=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 0 & 0 & 1 & 0\end{bmatrix} \begin{bmatrix} \sum_{i=0}^N F_i^2 \\F_{N+1}F_N\…

$$A=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$ $$F=\begin{bmatrix} 1 \\ 0 \end{bmatrix}$$ としたときの、 $$(A^n+A^{2n}+...+A^{mn})F$$$$=A^n \frac{E-A^{mn}}{E-A^n} F$$ の第二成分が答え。 testestestさんに教えていただいた解法 フィボナッチ…

(A+kD)%B>Cまたは(A+kD)

No.699 ペアでチームを作ろう２ - yukicoder 本当に何も考えずに全探索すると12!＝479001600回の計算が必要で間に合わない。 ペア(a,b)とペア(b,a)を同一視すると、12!/(2)^6=7484400回の計算にまで落ちる。C++ではこれで通るようだが、Javaでは全然駄目だ。…

https://www.ei1333.site/problems/14 解説を読んだ。 {1,2,3,...,N-1,N}を分割する方法の数をベル数という。B_Nで表す。 ベル数は i組のグループに分けるときの分け方についてそれぞれ包除原理を用いて求めている。 ここで、和を取る順序を変更する。k^N/k!…

問題 https://beta.atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_e 数直線上に Aさんと Bさんがいる。Aさんと Bさんの距離は L だけ離れている。Aさんと Bさんはそれぞれ同時に動く。Aさんは 現在地を xとすると x -1, x, x +1のいずれか…

https://beta.atcoder.jp/contests/arc090/tasks/arc090_c 問題 無向グラフ G が与えられる。 2頂点 S、T が与えられる。 A さんは頂点 S から頂点 T に向かう 。Bさんは頂点 T から頂点 S に向かう。A さんも B さんも最短路をとる。 このとき Aさんと Bさ…

問題