きたまさ法に関する記事です． よすぽさんの記事 を参照して書きました． 問題設定 整数 $ d_0 , \ldots, d_{ k - 1 }$ と $a_0, \ldots, a_{k - 1}$ が与えられている． 漸化式 $ a_{n + k} = d_{0} a_{n} + \cdots + d_{ k - 1 } a_{n + k - 1}$ で定義される数列の $a_n$ を $O( k^2 \log n )$ で求める． 行列 $$ A = \begin{bmatrix} d_{ k - 1 } &\cdots & \cdots & d_{ 0 } \\ 1 & & \Large{0} & 0 \\ & \ddots & & 0\\ \Large{0} & & 1 & 0 \\ \end{bmatrix} $$...
二項係数 binom(n, r) を，小さい素数 p に対して mod p で求める方法に関する記事です． 観察 p = 3 に関していくつか書いてみると次のようになっている． 0 1 1 1 1 2 1 2 1 10 1 0 0 1 11 1 1 0 1 1 12 1 2 1 1 2 1 20 1 0 0 2 0 0 1 21 1 1 0 2 2 0 1 1 22 1 2 1 2 1 2 1 2 1 100 1 0 0 0 0 0 0 0 0 1 101 1 1 0 0 0 0 0 0 0 1 1 102 1 2 1 0 0 0 0 0 0 1 2 1 110 1 0 0 1 0 0 0 0 0 1 0 0 1 111 1 1 0 1 1 0 0 0 0 1 1 0 1 1 112 1 2 1 1 2 1 0 0 0 1 2 1 1 2 1 120 1 0 0 2 0 0 1 0 0 1 0 0 2 0 0 1 こんな感じの構造になっている:...
Lagrange補間に関する記事です． 要約 $$ f(x) = \sum_{i = 0}^{k}\frac{ f(i) }{ (-1)^{k - i} \; i ! \; (k - i) ! } \cdot \frac{ 1 }{ x - i } \cdot \prod_{j=0}^{k} ( x - j ) $$ 詳細 \( k \) 次多項式 $f(x)$ について，$x = 0, \ldots, k$ の値が，$f(0) = v_0, \ldots, f(k) = v_k$ と分かっているときに， $f(x)$ (の各係数) を決める方法． 連立方程式を解く方法だと，逆行列を計算する必要があるから，\( \Omega( k^3 ) \) になってしまうが， Lagrange補間だと，$O(k^2)$ で済む． $I = \{0, \ldots, k\}$, $I_i = I \setminus \{ i \}$ とする．$i = 0, \ldots, k$ について，$k$ 次の多項式 $g_i(x)$ を， 次で定義する．...
行列木定理についての記事です． これを使う問題が，第二回日本最強プログラマー学生選手権 の G - Spanning Tree として出題されました． 定理 自己ループのない無向グラフ $G$ がある．頂点を $1, \ldots, N$ とする． 対称 $N\times N$ 行列 $A = (a_{ij})$ を，次で定める: $a_{ii} = $ 頂点$i$の出次数 $a_{ij} = - ( i \text{と} j \text{を結ぶ辺の数} )$ このとき，A のすべての余因子は等しく，G の全域木の数と一致する． 例 上のグラフでは， $$ A = \begin{bmatrix} 3 & -1 & 0 & -2 \\ -1 & 3 & -1 & -1 \\ 0 & -1 & 2 & -1 \\ -2 & -1 & -1 & 4 \end{bmatrix} $$...
CodeForces Round #431 (Div.2) E - Goodbye Souvenir についての記事です． 問題へのリンク https://codeforces.com/contest/849/problem/E 経緯 Yoika さんが主催している Morningforces というバーチャルコンテスト で出て，解けませんでした． 公式解説 を読んだのですが，最後に出てくる座標圧縮云々がよく分かりませんでした． 問題概要 整数列 $a = a_1, \ldots, a_k $ に対して，$m(a)$ を，$a$ に現れる各数 $x$ に対して，$x$ が最後に現れる位置と最初に現れる位置との差の総和として定義する．例えば，$m(1, 2, 3, 1, 3, 2, 1) = (7-1) + (6-2) + (5- 3) = 12$．最初に長さ n の整数列 a が与えられる．各要素は1以上n以下．次の2種類のクエリ (全部で$m$個) を処理せよ．$ 1 \leq n, m \leq 100,000$． p, x が与えられて，aのp番目の要素をxに書き換える． l, r が与えられて，$ m(a[l:r]) $ を求める． 解法 ということで，実装手段を除いては公式解説をなぞっています．...
C++ での乱数の使い方のメモです． 典型的なコード ll n; cin >> n; random_device rand_dev; mt19937 rng(rand_dev()); uniform_int_distribution<ll> dist(1, n); for (ll i = 0; i < 10; i++) cout << dist(rng) << " "; cout << endl; クラス random_device マニュアル オブジェクトは乱数発生器．non-deterministic な乱数を生成する． operator() を実行すると，unsigned int の乱数が返り，状態が進む． 実行は高価である可能性がある． クラス mt19937 マニュアル 32bitメルセンヌツィッター乱数発生器 64bitメルセンヌツィッター乱数発生器 の mt19937_64 というクラスもある． o.operator() を実行すると，uint_fast32_t の乱数が返り，状態が進む． コンストラクタに seed を渡す． デフォルトコンストラクタは引数をとらず，seed = 5489u を用いる．したがって，次のように書けば，どの実行でも同じ値が生成される． mt19937 rng; クラス uniform_int_distribution マニュアル 乱数分布を一様分布とする．constructor に a, b を指定すると，a以上b以下の一様分布． T は int や ll など．デフォルトは int． operator() は，引数に乱数発生器を取り，一様分布を生成する． 他の乱数分布クラスとコンストラクタの例: uniform_real_distribution<double> dist1(a, b); normal_distribution<double> dist2(mean, stddev);
AtCoder Regular Contest (ARC) 056 D - サケノミ についての記事です． 問題へのリンク 状況 解けないだけではなく，答を見てもなかなかわからなかったので，整理するために書いています．下記を参考にしています． 公式解説 kmjpさんのブログ 解法 時刻 $2j+1$ にドリンクを飲むような飲み方全部に関する，時刻 $2j+1$ 時点での美味しさの総和の最大値を $x(j)$ とする． 時刻 $2i$ に全部のグラスが空だったとき，半開区間 $(2i, 2j]$ に属する時刻に注がれるドリンクの美味しさの総和を $y(i, j)$ とすると， $x(j) = \max \{ x(i) + y(i, j) \mid i < j \} $ である．ここで，$z(i, j) = x(i) + y(i, j)$ と書くことにする．時刻 $j$ に注がれるドリンク全体の集合を $P$ とし，$ p \in P $ に対して時刻 $2j$ の一回前にドリンク $p$ が注がれる時刻を $l_p$ とする (時刻 j が初回なら，$l_p = 0$ とする)．すると，次が成り立つ．...
ABC237 Ex Hakata を解くのに必要だった Dilworth の定理他に関する記事です．