Posts

ABC399-F Range Power Sum が， 積の和典型だとのことなので，関連記事へのリンクなど． リンク 積の和典型 - ei1333の日記 ABC399-F 問題概要 問題へのリンク $A = (A_1, \dots, A_N)$ が与えられる．次を mod 998244353 で求めよ: $$ \sum_{1 \leq l \leq r \leq N}\left( \sum_{l \leq i \leq r} A_i \right)^K $$ 制約: $N \leq 2\times 10^5$, $K \leq 10$． 解法 (累積和で2項展開しても解けるが，それは置いといて…) 以下， 公式解説 より． 次のように言い換えられる． ボールが $A_i$ 個入った箱が一列に並んでいる． 箱の間に，2個の仕切りを入れる． 2つの仕切りの間にあるボールに，$1, 2, \ldots, K$ と書かれたラベルを1枚ずつ貼る 仕切りの入れ方とラベルの貼り方をセットで考えて，この方法の数が，求める答になる． DP で求める． dp[i][j][k] = (箱 i まで見て，仕切りを j 個入れていて，ラベルを k 枚貼るような方法の数)

畳み込みやゼータ変換やメビウス変換に関するメモ

WolframAlpha への入力方法のメモです

std::map に「挿入か更新をする」ときの idiom をすぐに忘れてしまうのでメモしておく． std::map<S, T> mp; と宣言されているとする． 1. 無条件で，s の値を t にする 通常は次で良い: mp[s] = t; もともと s が有ったか無かったのかも知りたい場合や，s へのイタレータも欲しい場合には，次のようにする: auto [it, b] = mp.insert_or_assign(s, t); b には，挿入が行われたかどうかが設定されるので，b が false なら，もともとキー s が存在していたことがわかる．it は s へのイタレータ． 2. キー s が無ければ，値を t にする． 次のように書くと，s の探索が2回走ってしまう． if (mp.find(s) == mp.end()) mp[s] = t; 次のようにすれば 1回ですむ． mp.emplace(s, t); もともと s が有ったか無かったのかも知りたい場合や，s へのイタレータも欲しい場合には，次のようにする: auto [it, b] = mp.emplace(s, t); b には，挿入が行われたかどうかが設定されるので，b が false なら，もともとキー s が存在していたことがわかる．it は s へのイタレータ．...

set, multiset, priority_queue などの比較関数の指定方法

デバッグに失敗した，ないし，長時間かかった間違いの記録 ABC212E Safety Journey 問題へのリンク 2023/07/05 あさかつ 無向グラフが，完全グラフからM本の辺を除いたものとして与えられている． 除く辺は $(u, v)$ の形で与えられている． dp[i][j] = (i 回の繰返し後，頂点 j に到達できる方法の数) という DP で， 全体から 除いた辺の分を引く． $(u, v)$ と $(v, u)$ の両方を引かなければならないところ， $(u, v)$ しか引かなかった． ABC279F BOX 2023/07/05 あさかつ タイプミス 正: if (rx == -1 and ry == -1) { 誤: if (rx == -1 and ry == 1) { ARC164B 2023/07/09 コンテスト 誤読． 正: 木の好きな頂点を選んで出発できる 誤: 木の根から出発する ABC222E Red and Blue Tree 2023/08/02 あさかつ...

階段関数を表現するライブラリ intervalSet の説明です．

ダブリングを行うライブラリを書きました．ソースはこちら ． できること その1 $f : [0, N) \to [0, N)$ が与えられた時， $r \in [0, R]$ と $i \in [0, N)$ に対して $f^{r}(i)$ を 計算する． 典型的には: $N$ は $10^5$ くらい，$R$ は $10^{18}$ くらい，または $N$ も $R$ も $10^5$ くらいだが，何回も (たとえば $10^5$回くらい) 計算する その2 上の $f$ の他に，モノイド $(M, \oplus)$ と $m: [0, N) \to M$ が与えられて， $r, i$ に対して $\bigoplus_{k = 0}^{r - 1} m(f^{k}(i))$ を計算する． 使用法 その1 DoublingFRel オブジェクト d を作る． 上記 $R$，$N$，$f$ を doubling_from_func に与える． ll R = 100000, N = 100000; auto f = [&](ll i) -> ll { return (i * i) % N; }; auto d = doubling_from_func(R, N, f); 関数 $f$ の代わりにベクトルなどのコンテナを与えたいときには，doubling_from_container を用いる． ll R = 100000, N = 100000; vector<ll> vec(N); REP(i, 0, N) vec[i] = ....

復元方法も含めた最長増加部分列に関するまとめ

集合のハッシュに関する記事です

平方分割ライブラリを書きました

木DP と マージテクを使って解くときのコードスニペット

$$ \binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r} $$ 言わずもがな．パスカルの三角形 $$ \binom{n}{r} = \frac{n}{r} \binom{n - 1}{r - 1} $$ 定義から明らか． $$ \sum_{i = r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1} $$ Hockey-stick identity. 次のように1を繰り返し適用． $\binom{n + 1}{r + 1} = \binom{n}{r} + \binom{n}{r + 1} = \binom{n}{r} + \binom{n - 1}{r} + \binom{n - 1}{r + 1} = \binom{n}{r} + \binom{n - 1}{r} + \binom{n - 2}{r} + \binom{n - 2}{r + 1} = \dots$...

解法に詰まったとき，以下の方法が適用できないか，考えてみる． 二分探索 bit64倍高速化 convolution 半分全列挙 フロー CHT trie (期待値) = sum_i (i以上になる確率) deque はランダムアクセスが O(1) 区間 [a, b] を2次元平面の点 (a, b) で表現 区間の問題を距離の問題に言い直して Dijkstra (例題 ) 積の和典型 集合のハッシュ． Zobrist Hashing (有限集合の部分集合) 多重集合のハッシュ (例題 )

ABC354-G の解答とともに，関連する予備知識 (König の定理, Dilworth の定理) をまとめます