AtCoder Regular Contest 212 (Div. 2) A～F問題メモ

AtCoder Regular Contest 212 (Div. 2)

A - Four TSP

問題文

$1, 2, 3, 4$ の $4$ 頂点からなる完全グラフがあります。辺の数は $6$ つです。
あなたはこれから $6$ つの各辺に、総和が $K$ となるように正整数の重みを割り当てます。
$f(G)$ を以下で定義します。
- グラフ $G$ の全ての頂点を通るサイクルにおける辺の重みの総和の最小値
考えうる全ての $G$ に対する $f(G)$ の総和を $998244353$ で割ったあまりを求めて下さい。

制約

$6 \le K \le 5000$
入力される値は全て整数

解法

問題文で示されるようなサイクルは、3通りしかない。

①--②  ①--②  ①  ②
｜  ｜    ×    ｜×｜
③--④  ③--④  ③  ④

それぞれ使わない辺に着目すると、(①④, ②③), (①③, ②④), (①②, ③④) にグループ分けでき、これはちょうど元のグラフの6辺を被らずカバーする分け方であると気付く。

$A$: ①④に割り当てる重みと②③に割り当てる重みの合計
$B$: ①③に割り当てる重みと②④に割り当てる重みの合計
$C$: ①②に割り当てる重みと③④に割り当てる重みの合計

とすると、$A+B+C=K$ であり、サイクルではこのうち最大のもののみ使わないことになる。
つまり、$f(G)=K-\max(A,B,C)$ である。

①④と②③の中で重みの合計を $A$ とするような分け方は $A-1$ 通りであり、これは $B,C$ でも同様。
よって、$(A,B,C)$ を固定した組に付き、$(A-1)(B-1)(C-1)(K-\max(A,B,C))$ だけ答えに寄与する。

$K \le 5000$ より、$O(K^2)$ かけて $A,B,C$ を全探索できる。

Python3

def solve(k):
    ans = 0
    MOD = 998244353
    for a in range(2, k - 3):
        for b in range(2, k - a - 1):
            c = k - a - b
            cycle = a + b + c - max(a, b, c)
            ans += (a - 1) * (b - 1) * (c - 1) * cycle
            ans %= MOD
    return ans


k = int(input())
ans = solve(k)
print(ans)

B - Stones on Grid

問題文

$N$ 行 $N$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と呼びます。
あなたは $i=1,2,\ldots,M$ の順に以下を行います。
- 操作 $i$ : マス $(x_i, y_i)$ に石を $1$ つ置くか、石を置かないかどちらかを選ぶ。石を置いた場合はコストが $c_i$ かかり、置かなかった場合はコストがかからない。
ただし、「操作 $1$ では必ず石を置く」という条件を守る必要があります。

以下の目標を達成できるか判定し、達成できる場合はかかるコストの和の最小値を求めてください。
- 目標 : 任意の $i \ (1 \leq i \leq N)$ について、$i$ 行目に置かれた石の数と $i$ 列目に置かれた石の数が等しい。

制約

$1 \le N, M \le 2 \times 10^5$
$1 \le x_i, y_i \le N$
$1 \le c_i \le 10^9$
$(x_i, y_i)$ は相異なる
入力される値は全て整数

解法

このようなグリッドの問題で、行番号と列番号を辺で結び、グラフの問題に帰着する解法はたまにある。

$(x_1,y_1)$ に石を置いたら、（自明な $x_1=y_1$ の場合を除いて）$(*,x_1)$ と $(y_1,*)$ のどこかに石を置く必要がある。
たとえば $(y_1,k)$ に置いたら、また今度は $(k,*)$ に置く必要がある。

この伝播は、グラフと似ている。
行または列番号に対応した $N$ 頂点を用意し、操作は、頂点 $x$ から $y$ にコスト $c$ の有向辺に置き換えると、解法が見える。

「$i$ 行目に置かれた石の数と $i$ 列目に置かれた石の数が等しい」という条件は、置き換えた問題では「採用する辺を決めた結果、全ての頂点で、採用辺の入次数と出次数が等しい」となる。

つまり、操作 $1$ に相当する辺を含む有向サイクルを作れればよい。 $c_i \ge 1$ より複数のサイクルを作るのは無駄なので、最もコストが安いサイクル1つを考えればよい。

よって、$y_1→x_1$ の最短経路探索をすると解ける。

Python3

from heapq import heappop, heappush


def solve(n, m, stones):
    links = [[] for _ in range(n)]
    for x, y, c in stones:
        x -= 1
        y -= 1
        links[x].append((y, c))

    INF = 1 << 60
    dist = [INF] * n
    x0, y0, c = stones[0]
    x0 -= 1
    y0 -= 1
    dist[y0] = c
    q = [(c, y0)]
    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        if u == x0:
            break
        for v, c in links[u]:
            nc = cost + c
            if dist[v] > nc:
                dist[v] = nc
                heappush(q, (nc, v))

    if dist[x0] == INF:
        return -1
    else:
        return dist[x0]


n, m = list(map(int, input().split()))
stones = [list(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, stones)
print(ans)

C - ABS Ball

問題文

$N$ 個の白いボールがあります。はじめに各ボールを赤か青どちらかの色で塗ります。
これら $N$ 個の赤か青で塗られたボールを、$M$ 個の区別できる箱のいずれかに入れます。
あるボールの入れ方 $S$ に対し、$f(S)$ を以下で定めます。
- $i$ 番目の箱に入っている赤、青のボールの数をそれぞれ $a_i, b_i$ とする。
- $f(S)=\prod_{1\leq i \le M}|a_i-b_i|$
全てのボールの入れ方に対する $f(S)$ の総和を $998244353$ で割ったあまりを求めて下さい。

ただし、$2$ つのボールの入れ方が異なるとは、ある $i$ について $a_i,b_i$ の少なくとも一方が異なることを言います。
- 特に、同じ色のボール同士は区別しないことに注意してください。

制約

$1 \le N,M \le 10^7$
入力される値は全て整数

解法

積の和典型。毎度出てくる度に、詳細を覚えてなくてググってる気がする。
問題設定からなんとなくそれっぽさを感じて検索すると、いかにも問題に適用できそうな公式が出てくる。

積の和典型の3通りの証明 | Mathlog

$m \le n$ とする。
$x_1+x_2+...+x_m=n$ なる正整数の組 $(x_1,...,x_m)$ 全てに対する $x_1 x_2 ... x_m$ の総和は $\binom{n+m-1}{n-m}$

問題の設定における各箱の $|a_i-b_i|$ が、上の式における $x_i$ に相当する。
$|a_i-b_i|$ の全ての箱を通しての総和を $n$ に固定した場合の数は、二項係数で求められると分かる。

$n$ は、$N,N-2,N-4,...$ のように、$N$ と偶奇が等しい $M$ 以上 $N$ 以下の任意の値を取り得る。
∵「最初に、各箱に決められた個数を達成できる最小限のボール（赤いボールのみ、または青いボールのみ $|a_i-b_i|$ 個）ずつ、計 $n$ 個となるように入れ、余ったボールをどの箱の $|a_i-b_i|$ に影響を与えないように入れる」という手順で配ることを考えた場合、余ったボールが偶数なら、赤と青、2個イチで1つの箱に入れていけば、影響を与えず処理できる。一方、余ったボールが奇数個なら、これらをどの箱の $|a_i-b_i|$ にも影響を与えず入れることができない。

$n$ を固定した場合の答えへの寄与は、以下の積となる。

積の和典型により、$\binom{n+M-1}{n-M}$
各箱で、赤と青どちらのボールが多いかで、$2^M$
- これは、どの $n$ でも一緒なので最後にかけてもよい
余ったボールを2個イチにしたペア数を $k=\frac{N-n}{2}$ とし、重複を許して $M$ 個の箱に入れる方法 ${}_M\mathrm{H}_k$

階乗の前計算により、$O(N+M)$ で求められる。

Python3

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, m):
    MOD = 998244353
    facts, finvs = precompute_factorials(n + m, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    def nhr(n, r):
        return facts[n + r - 1] * finvs[n - 1] % MOD * finvs[r] % MOD

    pow2m = pow(2, m, MOD)

    ans = 0
    for i in range(n + m):
        x = n - i * 2
        if x < m:
            break
        tmp = ncr(x + m - 1, x - m)
        tmp *= nhr(m, i)
        ans += tmp
        ans %= MOD

    ans *= pow2m
    ans %= MOD
    return ans


n, m = list(map(int, input().split()))
ans = solve(n, m)
print(ans)

D - Two Rooms

問題文

$1,2,\ldots,N$ の番号が付けられた $N$ 人の人が居ます。
$i\neq j$ に対して、人 $i$ と人 $j$ の親密度は $A_{i,j}$ です。ここで、$A_{i,j}=A_{j,i}$ です。
$N$ 人それぞれに対して、部屋 $X$, 部屋 $Y$ のどちらか一方を割り当て、入ってもらいます。
人 $i$ が良い状態であるとは、以下を満たすことと定義します。
- (人 $i$ と同じ部屋に居る人全員の、人 $i$ との親密度の和) $\geq$ (人 $i$ と異なる部屋に居る人全員の、人 $i$ との親密度の和)

$N$ 人全員が良い状態になるような部屋の割り当てを $1$ つ出力してください。
なお、そのような割り当ては必ず存在することが証明できます。

制約

$2 \leq N \leq 50$
$-50 \leq A_{i,j} \leq 50$
$A_{i,j} = A_{j,i}$
$A_{i,i}=0$
入力される値は全て整数

解法

未証明だけど、$N$ 小さいし、割り当ては必ず存在するらしいし、貪欲で通るんじゃね、で通ってしまった。

人 $i$ にとっての条件は、整理すれば以下のようになる。

$\displaystyle \sum_j$ (人 $i$ と $j$ が同じ部屋に居る場合 $1$、違う場合 $-1$) $\times A_j \ge 0$

左辺を $S(i)$ とする。
全員が同じ部屋にいる場合、各 $i$ につき $S(i)$ は行列 $A$ を各行に付き和を取った値と等しくなる。

サンプル1
    部屋
S(1)  X   0  4 -2 -1  →   1
S(2)  X   4  0 -3 -5  →  -4
S(3)  X  -2 -3  0  2  →  -3
S(4)  X  -1 -5  2  0  →  -4

人 $j$ を別の部屋に移すと、$A$ の $j$ 行目と $j$ 列目が、全て正負反転すると見なせる。
これを $S(i)$ が負のものが無くなるまで繰り返せばよい。

    部屋
S(1)  X   0 -4 -2 -1  →  -7
S(2)  Y  -4  0  3  5  →   4    j=2を移動
S(3)  X  -2  3  0  2  →   3
S(4)  X  -1  5  2  0  →   6

S(1)  Y   0  4  2  1  →   7    j=1を移動
S(2)  Y   4  0  3  5  →  12    （この例ではAの要素が全て正になったが、
S(3)  X   2  3  0  2  →   7      Aの要素自体は負のものがあっても、
S(4)  X   1  5  2  0  →   8      各S(i)が正なら終了してよい）

実行制限時間内に必ず答えが求まる証明

Python3

def solve(n, aaa):
    ans = [0] * n
    while True:
        for i in range(n):
            if sum(aaa[i]) < 0:
                ans[i] ^= 1
                for j in range(n):
                    aaa[i][j] *= -1
                    aaa[j][i] *= -1
                break
        else:
            break
    return ''.join('XY'[i] for i in ans)


n = int(input())
aaa = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, aaa)
print(ans)

E - Drop Min

問題文

$(1,2,\ldots,N)$ の順列 $P$ と、空の配列 $A$ があります。
$P$ に対して以下の操作を $N-1$ 回行います。
- 隣接する $2$ 要素を好きに選ぶ。選んだうち小さい方の要素を $P$ から削除し、削除した要素の前後を結合する。削除した要素を $A$ の末尾に追加する。

最終的にできる長さ $N-1$ の数列 $A$ としてあり得るものの数を $998244353$ で割ったあまりを求めてください。

制約

$2 \le N \le 2\times 10^5$
$1 \le P_i \le N$
$P$ は $(1,2,\ldots,N)$ の順列
入力される値は全て整数

解法

「どういう数列が、$A$ としてあり得ないか」を考える。

「両隣が自分より小さい $P_i$」は消しようがない。そのような $P_i$ は、左または右にある自身より大きい要素 $P_j$ までの間にある数を全て消して、 $P_j$ と隣接することでやっと消せるようになる。

j     i        j        Pi=4 は、A においては (1,2) または (3) の後にしか、現れてはいけない
5  3  4  1  2  6  7     ※括弧内は順不同
                        ※どちらか一方の後であれば、もう片方よりは前になってもよい

3,4,1,2 だけに着目したとき、A における出現順は、
○ (1,2,4,3), (3,4,2,1) など 14通り
× (1,4,3,2), (4,3,2,1) など

i              j        Pi=5 は、A において
5  3  4  1  2  6  7     (3,4,1,2) が全て出現した後にしか現れてはいけない

一方、（初期状態を含め）左右いずれかで自身より大きい要素と隣り合った $P_i$ は、それ以降ならいつ $A$ に現れてもよい。

例えば $2$ は、$(2,6)$ などと選ぶことで初手から好きなタイミングで消せる。操作の過程で $6$ が消されたとしても、消された後に $6$ の代わりに $2$ の隣に来る要素は $6$ より必ず大きいので、やっぱり好きなタイミングで消せる状態は保たれる。（このことから逆に、好きなタイミングで $P_i$ を消しても「$P_i$ が存在することでそれまで消せていた他の要素が、消せなくなる」ような事態が発生しないこともわかる）

この「$P_i$ にとって、自身より先に出現していなければならない要素の集合」は、再帰的な包含関係にある。

例えば上例では、$P_i=4$ の配置に注意しながら $A$ における $(3,4,1,2)$ の並べ方を考慮したが、その次、$P_i=5$ にとっては、$(3,4,1,2)$ 全てが出現した後でないと出現してはいけないことが分かる。
$P_i=4$ の制約を満たすように求めた並べ方を以て、$P_i=5$ の制約を満たす並べ方を求めていく、という具合になる。

Cartesian Tree 上での木DPで、葉から求めていける。
ただし、左右のマージ条件の場合分けがなかなか難しい。

サンプル 3
N=24
   10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11
     ,24,_______________________________,
   10                  ,_______________,23,_________________,
                 ,___,22,__,                           ,___,20,
              ,14,        ,21,__,           ,________,19,      11
            ,8    5,     9     ,15,__,     18,_____,     16
          ,4        2         1     ,13        ,__,17
         3                         6          12,
                                                 7

以下を末端から確定させてゆく。

$l_v:=v$ の部分木以下の頂点の要素数
$p_v:=v$ の部分木以下の頂点の $A$ における並べ方の個数

それにあたり、以下の真偽値を前計算しておく。必要な箇所は後述する。

(a) 両隣のいずれかに、自身より大きい要素があるか
(b) 自身より左に、自身より大きい要素があるか
(c) 自身より右に、自身より大きい要素があるか

$v=N$ の場合はマージが特殊（そもそも $N$ は $A$ に出現しない）ので、 $v=N-1$ までの $l_v,p_v$ を求めていくとする。

葉頂点

葉に関しては簡単。

$\mathrm{DP}[v]=(1,1)$

葉以外の頂点に関しては、左右の子（あれば）をマージしつつ、自身をどこに割り込ませるかも考慮して自身の $l_v,p_v$ を計算していく。

葉以外の (a)=True の頂点

前述のように、(a)=True、つまり左右に自身より大きい頂点があるものは、$A$ においていつ出現してもよい。

子の個数は1個である。（2個だと (a)=True になり得ない。また葉頂点でもない）

その子を $u$ とすると、長さ $l_u$ の列のどこかに $P_i$ を挟み込めばよい。

$\mathrm{DP}[v]=(l_u+1,p_u (l_u+1))$

葉以外の (a)=False の頂点

初期状態の $P$ において両隣とも自身より小さいか、または端にあり唯一隣接する要素が自身より小さい頂点である。

子が1つの場合

端にあり、唯一隣接する要素が自身より小さい頂点である。

その子を $u$ とすると、$u$ の部分木以下の頂点が全て揃った後にしか $v$ は出現できない。最後尾にくっつけるしかないので、場合の数は子の $p_u$ を引き継ぐ。

$\mathrm{DP}[v]=(l_u+1,p_u)$

子が2つで、(b)も(c)もTrue

2つの子を $w,u$ とする。このいずれかの部分木以下の頂点が全て出現した後に、$v$ が出現できるようになる。

①$w$ 側の列の後に出現させるのは $\binom{l_w+l_u+1}{l_w+1} p_w p_u$
②$u$ 側の列の後に出現させるのは $\binom{l_w+l_u+1}{l_u+1} p_w p_u$
③重複している（両方の子の後に出現）のは $\binom{l_w+l_u}{l_w} p_w p_u$
$\mathrm{DP}[v]=(l_w+l_u+1, ①+②-③)$ となる。

子が2つで、(b)または(c)がFalse

対称的なので、(b)がFalseとする。

この場合、左側の子 $w$ 以下の頂点を全て消したところで、$v$ は消せるようにならない。
$v$ を消すためには右側の子 $u$ 以下を全て消すしかない。

よって、「$u$ 側の列の後に $v$ をくっつけたもの」と「$w$ 側の列」をマージすると考えればよい。

$\mathrm{DP}[v]=(l_w+l_u+1, \binom{l_w+l_u+1}{l_u+1})$ となる。

(c)の場合は $w,u$ が逆となる。

$N$

最後、$N$ についてマージする。

$N$ が1つの子しか持たない（初期状態で $N$ が端に位置）場合は、$p_{N-1}$ がそのまま答えとなる。

それ以外の場合、2つの子の列をマージすればよい。

$\binom{l_w+l_u}{l_w} p_w p_u$

Python3

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, ppp):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    ppp = [p - 1 for p in ppp]
    lefts = [-1] * n
    rights = [-1] * n
    stack = []
    for p in ppp:
        if len(stack) == 0:
            stack.append(p)
            continue
        while len(stack) > 0 and stack[-1] < p:
            q = stack.pop()
            lefts[p] = q
        if len(stack) > 0:
            q = stack[-1]
            rights[q] = p
        stack.append(p)

    left_edge = set()
    p = lefts[n - 1]
    while p != -1:
        left_edge.add(p)
        p = lefts[p]
    right_edge = set()
    p = rights[n - 1]
    while p != -1:
        right_edge.add(p)
        p = rights[p]

    is_leaf = [False] * n
    for i in range(n):
        left_is_large = ppp[i - 1] > ppp[i] if i > 0 else False
        right_is_large = ppp[i + 1] > ppp[i] if i < n - 1 else False
        is_leaf[ppp[i]] = left_is_large or right_is_large

    sizes = [0] * n
    patterns = [0] * n
    for p in range(n - 1):

        if lefts[p] == -1:
            if rights[p] == -1:
                sizes[p] = 1
                patterns[p] = 1
                continue
            sr = sizes[rights[p]]
            pr = patterns[rights[p]]
            if is_leaf[p]:
                sizes[p] = sr + 1
                patterns[p] = pr * (sr + 1) % MOD
            else:
                sizes[p] = sr + 1
                patterns[p] = pr
            continue
        if rights[p] == -1:
            sl = sizes[lefts[p]]
            pl = patterns[lefts[p]]
            if is_leaf[p]:
                sizes[p] = sl + 1
                patterns[p] = pl * (sl + 1) % MOD
            else:
                sizes[p] = sl + 1
                patterns[p] = pl
            continue
        sl = sizes[lefts[p]]
        pl = patterns[lefts[p]]
        sr = sizes[rights[p]]
        pr = patterns[rights[p]]
        if p in left_edge:
            tmp = ncr(sl + sr + 1, sr + 1)
        elif p in right_edge:
            tmp = ncr(sl + sr + 1, sl + 1)
        else:
            tmp = ncr(sl + sr + 1, sl + 1)
            tmp += ncr(sl + sr + 1, sr + 1)
            tmp -= ncr(sl + sr, sl)
        tmp *= pl * pr % MOD
        sizes[p] = sl + sr + 1
        patterns[p] = tmp % MOD

    if lefts[n - 1] == -1:
        return patterns[rights[n - 1]]
    if rights[n - 1] == -1:
        return patterns[lefts[n - 1]]
    sl = sizes[lefts[n - 1]]
    pl = patterns[lefts[n - 1]]
    sr = sizes[rights[n - 1]]
    pr = patterns[rights[-1]]
    ans = ncr(sl + sr, sl) * pl * pr % MOD
    return ans

n = int(input())
ppp = list(map(int, input().split()))
ans = solve(n, ppp)
print(ans)

F - Add Integer

問題文

整数 $N,M,X$ が与えられます。
以下の一連の操作を行い、長さ $N$ の非負整数列 $A$ を作ります。
- 長さ $2$ の整数列 $A=(A_1,A_2)$ を自由に決める。
- その後、$A$ に対して以下の操作を $N-2$ 回行う。
  - $k=|A|$ とする。$x=A_{k-1},y=A_k$ とする。$A$ の末尾に $x+y$ または $y−x$ を追加する。

また、整数列 $A$ が良い数列であるとは、以下を満たすことを言います。
- $0 \le A_i \le M \ (1 \le i \le N)$
- $A_N=X$

操作によって得られる全ての良い数列に対する $A_1 \times A_2$ の総和を $998244353$ で割ったあまりを求めてください。

制約

$3 \leq N \leq 2 \times 10^5$
$1 \leq X \leq M \leq 2 \times 10^5$
入力される値は全て整数

解法

先頭から考えようとすると、毎回2通りの選択肢があるため候補が指数的に膨れ上がり手に負えない。
法則があるかと思って愚直を観察するも、あまりわかりやすい法則も見えない。

実は、全ての項が非負という条件から、 $Y=A_{N-1}$ を固定して末尾2項から考えると $A_{N-2},...,A_2,A_1$ までが一意に定まる。いやぁ、これは目から鱗だ。

略証

とはいえ、$Y$ は $0～M$ の値を取り得る。各場合を毎回 $O(N)$ かけて愚直に $A_1$ まで復元していたら、$O(NM)$ でTLEとなる。 $X,Y$ から $A_1$ を求める操作に $O(N)$ かけてはダメで、一気に何項かを飛ばして計算したい。

いくつか例を見てみる。

X=60, Y=11
60, 11, 49, 38, 11, 27, 16, 11, 5, 6, 1, 5, 4, 1, 3, 2, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...

Y=12
60, 12, 48, 36, 12, 24, 12, 12, 0, 12, 12, 0, 12, 12, 0, 12, 12, 0, 12, 12, 0, ...

Y=13
60, 13, 47, 34, 13, 21, 8, 13, 5, 8, 3, 5, 2, 3, 1, 2, 1, 1, 0, 1, 1, 0, ...

観察すると、以下のようになっている。
この仮定が正しいことは、$A_{i-1}=|A_{i}-A_{i+1}|$ の初項の大小関係をいろいろ場合分けすると、ちゃんと示せる。

しばらく、$3$ 個周期で $Y$ が出現する。
- その時、各 $Y$ の直前の値 $x$ は、$X-2Y,X-4Y,...$ と $2Y$ ずつ減っていく。
$x \lt 2Y$ になったら $3$ 個周期は止まる。
- 1ステップ進めて $X←Y, Y←|x-Y|$ とした後、再び同じことが繰り返される。
$0$ が出現したら、以降は $g=\mathrm{GCD}(X,Y)$ として、$g,g,0,g,g,0,...$ が繰り返される。

この法則によって、一気に先の項の値を求められる。ユークリッドの互除法に似たアルゴリズムで可能となる。

$Y$ の繰返しで、$x \lt 2Y$ となるまでの項数は $3\lfloor \frac{X}{2Y} \rfloor$ と計算できるので、ステップを一気に進められる。
$0$ となる（またはその前に $N$ 回に到達する）までのステップは $O(\log{\max(X,Y)})$ 回で抑えられるため、全体で $O(M \log{M})$ で解くことができる。

Python3

def solve(n, m, x):
    def naive(x, y, k):
        for _ in range(k):
            x, y = y, abs(x - y)
        return x, y

    def sub(x, y):
        k = n - 2
        while k > 10 and y != 0:
            d = x // y // 2
            if k <= 3 * d:
                step, k = divmod(k, 3)
                x -= step * y * 2
                break
            k -= 3 * d + 1
            x -= y * 2 * d
            x, y = y, abs(x - y)

        if y == 0:
            k %= 3

        x, y = naive(x, y, k)
        return x * y

    MOD = 998244353
    ans = 0
    for y in range(m + 1):
        ans += sub(x, y)
        ans %= MOD

    return ans


n, m, x = list(map(int, input().split()))
ans = solve(n, m, x)
print(ans)

目次

AtCoder Regular Contest 212 (Div. 2) A～F問題メモ

A - Four TSP

問題文

制約

解法

B - Stones on Grid

問題文

制約

解法

C - ABS Ball

問題文

制約

解法

D - Two Rooms

問題文

制約

解法

E - Drop Min

問題文

制約

解法

葉頂点

葉以外の (a)=True の頂点

葉以外の (a)=False の頂点

子が1つの場合

子が2つで、(b)も(c)もTrue

子が2つで、(b)または(c)がFalse

$N$

F - Add Integer

問題文

制約

解法