まずパスで考察すると見通しが良い

二次元ゲームは図を書くとよい

H - Median Game

困ったら二分探索

2023-04-05

Universal Cup Stage.10 (Zhejiang) A - Atcoder Problem

$O(N\log N\log M)$ と重めだが高度な fps を用いない方法。

問題概要

$n=1,2,\ldots,N$ について、以下を満たす長さ $n$ の数列 $A$ の個数を求めよ。

$0 \le A_1 \le A_2 \le \ldots \le A_n \le M$
$A_1 \oplus A_2 \oplus \ldots \oplus A_n = X$

$1 \le N \le 10^5$
$0 \le M,X < 2^{60}$

解法

$M$ に $1$ を足して、 $0 \le A_1 \le A_2 \le \ldots \le A_n < M$ と言い換えておきます。また、 $n$ の時の答えを $f_n$ と表記します。

ここで、 $0 \le B_1 < B_2 < \ldots < B_n < M$ かつ $\bigoplus_i B_i = X$ を満たす $B$ の個数を $g_n$ とおくことにして、 $F:=\sum_n f_nx^n, G:=\sum_n g_nx^n, H := \sum_i \binom{M-1+i}{i}x^{2i}$ とすると、 $F=GH$ が成り立ちます。(これは ABC288Ex の解説とかで触れられてると思います)よって、 $g_n$ を求めることができればよいです。

今後、以下が成り立つことを利用します。( $N$ が偶数の場合未証明、実験で導きました)

かつを満たすの個数をとおくと、
- $N$ が奇数の場合、 $h(X)$ は一様分布。
- $N$ が偶数の場合、 $h(X)$ は $X=0$ を除いて一様分布。また、 $h(0)-h(1)=(-1)^{N/2}\binom{2^{M-1}}{N/2}$ が成り立つ。

KUPC2017K の別解と同じように、上の桁から考察していきます。いま $k$ 桁目を見ているとします。 $M,X$ ともに $k$ 桁目が $0$ ならば $k-1$ 桁目に移ります。 $M$ のみが $0$ ならば答えは $0$ です。 $M$ の $k$ 桁目が $1$ とします。

ここで、 $B$ の $k$ 桁目について考察します。 $0$ が連続したあと $1$ が( $X$ の $k$ 桁目が $1$ なら奇数個、そうでないなら偶数個)連続する形になります。ここで、前半の $0$ が連続する部分の下の桁は $[0,2^k)$ の値を一様に取れることが重要で、もし $0$ の連続する個数が奇数ならこの時点で答えがわかります(上の桁が $1$ である部分が何であろうと関係なくなるので)。また、 $0$ の連続する個数が偶数の場合も、 XOR が $0$ である場合以外は一様ですから、一様として答えを求めた後、 $0$ の長さを $2t$ として、 $(n-2t,M \bmod 2^k, X \bmod 2^k)$ についての問題の答えを用いて「補正」をしてあげればよいです。ここで、持つべき必要がある状態を考えると、「 $g_{k,n}:=(n,M\bmod 2^k,X\bmod 2^k)$ の時の答え」のみであり、 $k$ が小さいほうから計算していくことができます。状態遷移が畳み込みの形になっていることに気を付けると、 $O(N\log N\log M)$ でこの問題が解けます。

2022-10-24

No.2084 Mex Subset For All Sequences / No.1856 Mex Sum 2　高速解法

No.2084 Mex Subset For All Sequences / No.1856 Mex Sum 2 を統一的に解き、かつ計算量を落とす方法を紹介します。

問題リンク

yukicoder.me
yukicoder.me

問題概要

No.2084 の方の設定を採用します。(No.1856 も与えられた $M$ に $1$ を足せば同じ状況になります)
$0$ 以上 $M$ 未満の整数からなる長さ $N$ の整数列 $A$ すべてについて、すべての非空部分列の $\mathrm{mex}$ の和を考え、その和を $998244353$ で割った余りを求めてください。

解法

主客転倒と包除原理を用いて立式して、適当に変形します。
$\displaystyle \begin{aligned} &\sum_{k=1}^N \binom{N}{k} M^{N-k}\sum_{t=1}^{\min(N,M)} \sum_{l=0}^t \binom{t}{l} (-1)^l (M-l)^k \\ =& \sum_{k=0}^N \binom{N}{k} M^{N-k} \left(\sum_{l=0}^{\min(N,M)} (-1)^l (M-l)^k \sum_{t=l}^{\min(N,M)} \binom{t}{l}-M^k\right) \\ =& \sum_{k=0}^N \binom{N}{k} M^{N-k} \left(\sum_{l=0}^{\min(N,M)} (-1)^l (M-l)^k \sum_{t=0}^{\min(N,M)-l} \binom{t+l}{l}\right) - (2M)^N \\ =& \sum_{k=0}^N \binom{N}{k} M^{N-k} \left(\sum_{l=0}^{\min(N,M)} (-1)^l (M-l)^k \binom{\min(N,M)+1}{l+1}\right) - (2M)^N \\ =& \sum_{l=0}^{\min(N,M)} (-1)^l\binom{\min(N,M)+1}{l+1} \sum_{k=0}^N \left(\binom{N}{k} M^{N-k} (M-l)^k \right) - (2M)^N \\ =& \sum_{l=0}^{\min(N,M)} (-1)^l\binom{\min(N,M)+1}{l+1} (2M-l)^N - (2M)^N \\ \end{aligned}$

より、この問題を $O(\min(N,M)\log \min(N,M))$ で解くことができました。 No.2084 のような状況ならば、線形篩を用いれば時間計算量 $O(M + M\log N/\log M)$ になります。

2022-09-27

CODE FESTIVAL 2017 Elimination Tournament-F Unicyclic Graph Counting の準線形解法

CODE FESTIVAL 2017 Elimination Tournament F-Unicyclic Graph Counting を時間計算量 $O(N\log^{2} N)$ で解く解法を紹介します。

問題リンク

atcoder.jp

問題概要

長さ $N$ の正整数列 $d$ が与えられる。頂点 $i$ の次数が $d_i$ であるような $N$ 頂点 $N$ 辺の単純連結グラフの個数を ${} \bmod {10^{9}+7}$ で求めよ。

$3 \le N$
$1 \le d_i \le N-1$
$\sum_i d_i = 2N$

定式化

まず、 $d_i=2$ となる頂点しか存在しない場合、解は $\frac{(N-1)!}{2}$ です。以下、 $d_i \neq 2$ を満たす頂点が存在するとします。

頂点の集合の中から、サイクルとして選択する頂点の集合を $S$ 、選択しない頂点の集合を $T$ とします。また、 $|S|=k, \sum_{v \in S} (d_v-2) = s$ とします。

ここで、 $3 \le k \le N-1$ とします。(前提より、この仮定を満たさない $k$ について、解は $0$ です)

また、いったん $2 \le \min_{v \in S} d_v$ 、 $1 \le s$ としておきます。

この時の解は(サイクルの作り方) $\times$ (サイクルを $1$ つの頂点としてみた時の木の数) $\times$ (サイクルから出る辺と頂点の対応付け) の形で書け、

$\displaystyle \frac{(k-1)!}{2} \times \frac{((N-k+1)-2)!}{\prod_{v \in T} (d_v-1)! \times (s-1)!} \times \frac{s!}{\prod_{v \in S} (d_v-2)!}$

と表せます。これを変形すると

$\displaystyle \frac{(N-k-1)!(k-1)!}{2 \times \prod_i (d_v-1)!} \times \prod_{v \in S} (d_v-1) \times s$

となります。この式では $\min_{v \in S} d_v=1$ や $s \le 0$ のケースが $0$ を返すので、さっきの $2$ つの仮定は取り除いて ok です。

ここで、 $t_i:=d_i-1$ とします。

すべての $0 \le k \le N$ について、 $\{1,2,\ldots,N\}$ の部分集合 $S\ (|S|=k)$ についての $\prod_{v \in S} t_v \times \sum_{v \in S} (t_v-1)$ が求まれば、解は高速に求まります。

ここで、いったん和の部分を無視したとき、 $k$ についての答えは $[ x^{k}] \prod_i (1+t_ix)$ と書けます。

和の部分が入るときのみ $t_i$ ではなく $t_i(t_i-1)$ をかけることを考えると、 $k$ についての答えは $\displaystyle[x^{k}] \sum_j \left((t_j(t_j-1)x) \times \prod_{i \neq j} (1+t_ix)\right)$ と書けます。

これを変形すると $\displaystyle[x^{k}]\prod_i (1+t_ix) \sum_j \frac{t_j(t_j-1)x}{1+t_jx}$ となります。 $\displaystyle f:=\prod_i (1+t_ix), g:=\sum_i \frac{t_i(t_i-1)x}{1+t_ix}$ とすると、 $k$ についての答えは $[x^{k}] f\times g$ と書けます。

ここで、 $f,g$ ともに次数が小さいものからマージするテクニックで $O(N\log^{2} N)$ で求めることができます。

よって、この問題を $O(N\log^{2} N)$ で解くことができました。

2021-08-01

ABC212-G Power Pair の高速解法

ABC212-G Power Pair の素因数分解に $X(N)$ 時間かかるとしたときの $O(X(P-1) + \log(P))$ 解法を紹介します。

問題リンク

atcoder.jp

問題概要

$0 \le x, y \lt P$ を満たす $(x, y)$ の組であって、ある正整数 $n$ が存在して $x^ n \equiv y \pmod {P-1}$ を満たすものの個数 $\bmod {998244353}$ を求めよ。

問題変形

まず、ある素数 $P$ について原始根 $g$ がかならず $1$ つは存在する(参考)ことと、 $a, b$ のうちどちらかが $0$ ならばもう一方も $0$ でなければ条件が成り立たないことから、問題は次のように言い換えられます。

$0 \le a, b \lt P-1$ を満たす $(a, b)$ の組であって、ある正整数 $n$ が存在して $a \times n \equiv b \pmod {P-1}$ を満たすものの個数 $+\ 1\bmod {998244353}$ を求めよ。

本題

ここで、 $a$ を固定した時にありうる $b$ の個数は $\displaystyle\frac{P-1}{\gcd(a,P-1)}$ ですから、求めるものは $\displaystyle\sum_{a=0}^{P-2}\frac{P-1}{\gcd(a,P-1)}+1$ です。

この値は $\displaystyle \sum_{d|(P-1)} \left(\frac{P-1}{d} \times f\left(\frac{P-1}{d}\right)\right)+1$ に等しいです(ただし、 $f(x)$ は $\gcd(a,P-1)=x$ を満たす $a(0 \le a \lt P-1)$ の個数を表します)

ここで、 $f(x)$ について考えてみます。 $\gcd(a,P-1)=x$ を満たす $a(0 \le a \lt P-1)$ の個数は $\displaystyle\gcd\left(a',\frac{P-1}{x}\right)=1$ を満たす $\displaystyle a'\left(0 \le a' \lt \frac{P-1}{x}\right)$ の個数と等しく、またこの値は $\displaystyle\phi\left(\frac{P-1}{x}\right)$ ( $\phi(x)$ はオイラーのφ関数を表します)と等しいです。

これより、求める値は $\displaystyle \sum_{d|(P-1)} \left(\frac{P-1}{d} \times \phi\left(\frac{P-1}{d}\right)\right)+1$ です。

ここで、あとでわかりやすくするために $\displaystyle \sum_{d|(P-1)} (d \times \phi(d))+1$ と変形しておきます。

ところで、 $\phi(n)$ は $n$ が $\displaystyle \prod_{i=0}^{s-1} {p_i}^{e_i}$ ( $i \neq j$ ならば $p_i \neq p_j$ ) と表せるとき、次のように求められます。

$\displaystyle \phi(n)=\prod_{0 \le i \lt s \land e_i \neq 0} ({p_i}^{e_i} - {p_i}^{e_i-1})$

$n$ の約数はすべての $i$ について $0 \le t_i \lt e_i$ を満たす数列 $t$ を用いて $\displaystyle \prod_{i=0}^{s-1} {p_i}^{t_i}$ と表すことができ、またこの形で表現できるもののみが $n$ の約数です。

これらより、求めるものは $P-1 = \displaystyle \prod_{i=0}^{s-1} {p_i}^{e_i}$ として $\displaystyle \sum_{t_0=0}^{e_0} \sum_{t_1=0}^{e_1} \cdots \sum_{t_{s-1}=0}^{e_{s-1}} (\prod_{i=0}^{s-1} {p_i}^{t_i} \times \prod_{0 \le i \lt s \land t_i \neq 0} ({p_i}^{t_i}-{p_i}^{t_i-1}))+1$ です。これを整理して $\displaystyle \sum_{t_0=0}^{e_0} \sum_{t_1=0}^{e_1} \cdots \sum_{t_{s-1}=0}^{e_{s-1}} \prod_{0 \le i \lt s \land t_i \neq 0} ({p_i}^{t_i} \times ({p_i}^{t_i}-{p_i}^{t_i-1}))+1$ です。