Sum of Multiplicative Function on Powerful Numbers

multiplicative function $f(n)$ に対し、$F(n) := \sum\limits_{m: \text{ powerful number}} f(m)$ とする。ただし、ある多項式 $g$ が存在して、任意の素数 $p$ に対して $f(p^2) = g(p)$ とかけるとする。このとき、$F(n)$ を時間計算量 $O(n^{1/3} \log…

Sum of Multiplicative Function

multiplicative function $f(n)$ に対し、$F(n) := \sum_{1 \le i \le n} f(i)$ とする。ただし、ある多項式 $g$ が存在して、任意の素数 $p$ に対して $f(p) = g(p)$ とかけるとする。このとき、$F(n)$ を時間計算量 $O(n^{2/3})$、空間計算量 $O(\sqrt{n})$…

Find Linear Recurrence with Polynomial Coefficients

ある数列 $(a_0, a_1, a_2, \dots)$ が P-recursive (holonomic) であった場合に、$\sum_{i=0}^{k} f_{i}(n) \cdot a_{n-i} = 0$ ($n \ge k$) を満たすような($d$ 次以下の)多項式係数 $f_0, \cdots, f_k$ を見つける方法です。

格子点の数え上げの高速化

凸関数・凹関数で囲まれる範囲の格子点の個数の数え上げなどを、凸包を用いて高速化するテクニックです。半径 $n$ の円に含まれる格子点の個数を $O(n^{2/3})$ ほど、$1$ から $n$ までの約数の総和を $O(n^{1/3} \log{(n)})$ ほどで求めることができます。

Scary Sum

総和 $$ S(a, b, k) := \sum_{x=0}^{b-1} \left\lfloor\frac{ax}{b}\right\rfloor^k $$ を $\bmod{p}$(十分に大きな素数)で $O(k \log k \log(\min\{a, b\}))$ で求めます。ただし、$\gcd(a, b) = 1$ とします。

最小費用最大流の悪例題

蟻本に掲載されている最小費用流の実装で、$n$ を頂点数として、$O(2^{n/2} n^2 \log n)$ 時間かかる例題です。

二項係数 mod Prime Power

$\binom{n}{m} \bmod{p^e}$ を高速に解く。($n, m, p^e \lt 10^{300}$, $pe \lt 10^6$, $p$: 素数)

FFT と多項式乗算

任意 mod の多項式乗算を 4 回の FFT でやる方法。ここでは、mod は $2^{30}$ 以下を想定。

Wavelet Matrix 3D [2]

前回の実装を簡略化する。

Wavelet Matrix 3D

3 次元クエリに対応できる Wavelet Matrix を実装する。

最小費用流問題(Cost Scaling)[2]

前回の Cost Scaling の実装を改善する。

最大流(Dinic vs HI-PR)

最大流のアルゴリズムの Dinic と Highest Label Push Relabel (HI-PR) を比較する。

除算・剰余算の高速化

除算・剰余算の高速化のテクニック。

最小費用流問題(Cost Scaling)

最小費用流問題を Cost Scaling を用いて $O(V^2E \log{(VC)})$ で解く。

Wolstenholme Prime の探索

$10^9 \lt p \lt 2 \cdot 10^{9}$ の範囲について、Wolstenholme Prime を探す。

調和数 mod 素数

$\left(\sum _{i=1}^{n} \frac{1}{i}\right) \bmod{p}$ を計算量 $O(\sqrt{p} \log{p})$ で求める。

Binomial Sum mod 素数

二項係数の総和 $\left(\sum_{i=0}^{k} \binom{n}{i}\right) \bmod{p}$ を $O(\sqrt{p} \log{p})$ で求める。($0 \le k \le n \lt p$)

階乗 mod 素数

$n! \bmod{p}$ を計算量 $O(p^{1/2} \log{p})$ で求める。

一般最大マッチング / 一般最大重み付きマッチングの実装

一般最大マッチングと一般最大重み付きマッチングの実装例です。

母関数解法

母関数を用いて、機械的に解ける問題。

Diophantine Approximation

ある実数 $\alpha, \beta, \varepsilon > 0$ と整数 $N$ が与えられたとき、$$ \min_{0 \le i \le N} \{ \{\alpha i + \beta\} \}, \\ \mathop{\min \{i \mid i \in \mathbb{N}, \{\alpha i + \beta\} \lt \varepsilon\} } $$ を求める問題について考える。…

Polynomial Sum

djdolls さんの公式 QPOLYSUM - Editorial - CodeChef Discuss を、固有多項式を用いた一般的な方法で導出する。

FFT (NTT) 関連

FFT (NTT) を用いて $O(n^2)$ から $O(n \log{n})$ に高速化できるもの。 基本的に modulo $p$ で計算することを前提とする。