問題概要 問題へのリンク 長さ$N$の文字列 $S$ が与えられる．$S$ に現れる文字は B と P だけ． 次の操作によって，B を左に P を右に寄せ $S$ を BB...BPP...P という形にする． 操作の最小回数を求めよ． $S$ の長さ3の部分列をとり，その部分の B を左に，P を右に寄せる． つまり，1回の操作は，以下のいずれか: (あ) PPB $\to$ BPP (い) PBP $\to$ BPP (う) PBB $\to$ BBP (え) BPB $\to$ BBP 制約 $3 \leq N \leq 2\times10^5$ 解 tutorialへのリンク 略解．click to open 奇数番のみ，偶数番のみの列を考えると， 操作は，次のいずれかになっている: (ア) 奇数列の隣接入替，偶数列の隣接入替 (あ, う) (イ) 奇数列と偶数列の B, P の入替 (い，え) 全体としてみたときの転倒数を $r$ とする．(ア)では転倒数が2減り， (イ) では転倒数が1減る． 最終形を考えると，奇数列，偶数列の B, P の個数は決まっている． だから，(イ) の最低必要な回数 $x$ が決まる． 「最初に (イ) を $x$ 回行って，あとの操作はすべて (ア)」が実現できれば， それ以上回数は減らせない．...

問題概要 問題へのリンク 整数 $N \geq 1$ と，整数の multiset $ A, B$ が与えられる．$A$, $B$ の要素数は $N$ である． 整数 $K$ で，multiset $ \{ a \bmod K \mid a \in A \}$ が $B$ と等しくなるものがあるか判定し， あれば1つ与えよ． 制約 $1 \leq N \leq 10^4$，$0 \leq a_i, b_i \leq 10^6$ 解 tutorialへのリンク 略解．click to open そういう $K$ があれば $K$ は，$d := \sum_i a_i - \sum_i b_i$ の約数になる． ($10^{10}$ 以下の数の約数の個数の最大値は $2304$ 個である．)

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 へのイタレータ．...

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

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

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

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

木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$...

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

1000までの素数表 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, $10^9$ までの素数の分布 $n$ $10^n$ までの素数の数 1 4 2 25 3 168 4 1229 5 9592 6 78498 7 664579 8 5761455 9 50847534

ポテンシャル付きUnionFindです． 実装はこちら ． 使用法 UnionFind uf(N); // 普通のUnionFind (ポテンシャル無し) ld = uf.merge(a, b); // マージ．新しいリーダを返す ld = uf.leader(a); // リーダ ng = uf.num_groups(); // 全体のグループ数 ( == リーダの数) sz = uf.group_size(a); // a が属するグループのサイズ グループの要素のリストを得るためには，前処理として，GroupInfo を作る必要がある． これには，$O(N)$ かかる． auto gi = uf.group_info(); for (int i : gi.group(a)) cout << i << endl; // a が属するグループの要素の列挙 ポテンシャル付きにするためには，テンプレートパラメタで，ポテンシャルの型を渡す． (デフォルトの型は，UFDummyAlg なるものになっている) UnionFind<ll> uf1(N); UnionFind<ftwo> uf2(N); 必要があれば，零元，和，単項マイナスを渡すこともできる: UnionFind<ll> uf3(N, 0LL, plus<ll>(), negate<ll>()); ポテンシャル付きの時には，merge のときの第3引数に，ポテンシャルを渡さなければならない (省略不可)． merge の返却値は，ポテンシャルが無いときと同じで，リーダである．...