AtCoder Beginner Contest 423 E,F,G問題メモ

AtCoder Beginner Contest 423

E - Sum of Subarrays

• 長さ $N$ の整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
• $Q$ 個のクエリが与えられるので、それぞれについて答えを求めてください。
  • $i$ 番目のクエリでは、整数 $L_i, R_i$ が与えられます。
  • $A$ の区間 $[L_i,R_i]$ 内にある全ての「連続部分列の和」の総和を求めてください。
  • つまり、$\displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j$ を求めてください。

• $1 \leq N, Q \leq 3 \times 10^5$
• $1 \leq A_i \leq 100$
• $1 \leq L_i \leq R_i \leq N$
• 入力される値はすべて整数

$i^2A_i, iA_i, A_i$ のそれぞれの累積和を持つことで解ける。

• 解説 - AtCoder Beginner Contest 423

毎度おなじみのセグメント木解法。（思考停止ともいう）

「セグ木にのせるもの」と「マージする方法」を考えればよい。
結論から言うと、区間 $x$ に以下の5つの情報を持たせるとできる。

• $x_1$: 区間長
• $x_2$: 区間の $A_i$ の総和
• $x_3$: 区間の全ての部分列の総和の総和（求めたいもの）
• $x_4$: 部分列のうち、左端要素を使うものの総和の総和
• $x_5$: 部分列のうち、右端要素を使うものの総和の総和

 x
[ 1  2  3  4 ]

x4の対象となる部分列
  1
  1  2          x4 = (1)+(1+2)+(1+2+3)+(1+2+3+4) = 20
  1  2  3
  1  2  3  4

x5の対象となる部分列
           4
        3  4    x5 = (4)+(3+4)+(2+3+4)+(1+2+3+4) = 30
     2  3  4
  1  2  3  4

（※$x_5$ は $x_1,x_2,x_4$ から求められるので不要といえば不要。まぁあった方が考えやすい）

$a=(1,2,3),b=(4,5,6,7)$ とし、マージした区間を $c$ とすると、$c_1,c_2$ は自明な足し算で求められる。
$c_4$ は以下のようにして求められる。左右逆転して同様に $c_5$ も求められる。

[ 1  2  3  4  5  6  7 ]

c4の対象    a4
  1       ↙
  1  2
 _1__2__3_         b4
  1  2  3| 4     ↙
  1  2  3| 4  5
  1  2  3| 4  5  6
  1  2  3| 4  5  6  7
     ↑
   a2*b1

$c_3$ は、以下のようにして求められ、$a_3+b_3+a_5b_1+b_4a_1$ となる。

マージ境界をまたがないもの: a3, b3

またぐもの: 左右別にそれぞれがどれだけ寄与するかで考える

    a5             b4
        3      4
     2  3  ×  4  5
  1  2  3      4  5  6
               4  5  6  7

  a5 側の各部分列は、右をどこまで伸ばすかが b1 通りずつある → a5 * b1
  b4 側の各部分列は、左をどこまで伸ばすかが a1 通りずつある → b4 * a1

これでマージができるので、セグメント木に載せると $O(N + Q \log{N})$ でできる。

Python3

from atcoder.segtree import SegTree


def solve(n, q, aaa, queries):
    def merge(a, b):
        a0, a1, a2, a3, a4 = a
        b0, b1, b2, b3, b4 = b
        c0 = a0 + b0
        c1 = a1 + b1
        c3 = a3 + a1 * b0 + b3
        c4 = b4 + b1 * a0 + a4
        c2 = a2 + b2 + a4 * b0 + b3 * a0
        return (c0, c1, c2, c3, c4)

    # (長さ, 区間和, 全体合計, 左端を使うものの合計, 右端を使うものの合計)
    init = [(1, a, a, a, a) for a in aaa]
    sgt = SegTree(merge, (0, 0, 0, 0, 0), init)
    ans = []
    for l, r in queries:
        result = sgt.prod(l - 1, r)
        ans.append(result[2])
    return ans


n, q = map(int, input().split())
aaa = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, aaa, queries)
print('\n'.join(map(str, ans)))

F - Loud Cicada

• AtCoder 島には $N$ 種類のセミが生息しています。種類 $i$ のセミ ($1 \leq i \leq N$) は $A_i$ の倍数の年にのみ大量発生します。
• $1$ 年から $Y$ 年までの $Y$ 年間のうち、ちょうど $M$ 種類のセミが大量発生する年が何回あるかを求めてください。

• $1 \leq M \leq N \leq 20$
• $1 \leq Y \leq 10^{18}$
• $1 \leq A_i \leq 10^{18}$ ($1 \leq i \leq N$)
• 入力される値はすべて整数

素数ゼミをテーマとした問題。
包除原理っぽいが、いつもとはちょっと違い「ちょうど $M$ 種類」のものを求めたい。

いつもの包除原理なら $\displaystyle \sum_{S}(-1)^{|S|} f(S)$ などのような式（$f$ は適当な関数）になるが、 これは「少なくとも1つの条件に当てはまる」や「どの条件にも当てはまらない」$f(S)$ の合計を求めることになり、 ここからでは「ちょうど $M$ 個の条件に当てはまる」場合は求まらない。

N=3 M=2
  ┌──┐      □□□
┌┼─┐│    □■■□    黒いとこだけのf(S)を求めたい
││┌┼┼┐  □■□■□
│└┼┼┘│  □□■□□
└─┼┘  │      □□□
    └──

あるセミの種類の集合 $S=\{i_1,i_2,...\}$ に対し、 そいつらが揃って大量発生する周期は $\mathrm{LCM}(A_{i1},A_{i2},...)$ であり、 $Y$ 年間の中での発生回数は $C_S = \left \lfloor \dfrac{Y}{\mathrm{LCM}(A_{i1},A_{i2},...)} \right \rfloor$ である。

（※この時、LCMはまともに計算すると巨大になり得るので注意。 途中で $Y$ を超えたら $C_S=0$ に決まるので、計算を打ち切ってよい）

$C_S$ を、$|S| \ge M$ である全ての $S$ について計算しておく。
さらに、$|S|$ ごとに計算結果をまとめておく。$\displaystyle D_d = \sum_{|S|=d}C_S$

すると、答えは以下で求められる。（$N=4,5$ くらいで必死に書き出すとエスパーできる）

• $\displaystyle \sum_{d=M}^{N}(-1)^{d-M} \binom{d}{M} D_d$

証明は「真の答え」と「$C_S$ を合計しただけのダブりを含んだ答え $D_d$」の間に計算式をたて、式変形することで導出できる。

• 解説 - AtCoder Beginner Contest 423

Python3

from math import gcd


def iter_bit(bitset):
    i = 0
    while bitset:
        if bitset & 1:
            yield i
        i += 1
        bitset >>= 1


def solve(n, m, y, aaa):
    def ncr(n, r):
        result = 1
        for i in range(r):
            result *= n - i
            result //= i + 1
        return result

    cases = [0] * (n + 1)
    lcm_memo = [0] * (1 << n)
    lcm_memo[0] = 1
    for bitset in range(1, 1 << n):
        bc = bitset.bit_count()
        lsb = bitset & -bitset
        lcm = lcm_memo[bitset ^ lsb]
        if lcm > y:
            lcm_memo[bitset] = lcm
            continue
        a = aaa[lsb.bit_length() - 1]
        g = gcd(lcm, a)
        lcm = lcm // g * a
        lcm_memo[bitset] = lcm
        cases[bc] += y // lcm

    ans = 0
    pn = 1
    for i in range(m, n + 1):
        ans += pn * cases[i] * ncr(i, m)
        pn *= -1
    return ans


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

$H_S$ を、「$S$ に含まれる種類のセミのみが大量発生する年の数」とする。

前の解法の $C_S$ は「$S$ に含まれる種類のセミが大量発生する年の数」であり、他のセミも大量発生しているケースが含まれている。

$S$ をbitフラグで表し、たとえば $N=5, S=10110$ とすると、以下が成り立つ。

• $C_{10110} = H_{10110}+H_{10111}+H_{11110}+H_{11111}$

つまりは、$C_S$ は「$S$ を含む集合 $T$ 全てに対する $H_T$ の総和」なので、まさしく $H$ と $C$ はゼータ変換の前と後という関係になる。

$C$ から $H$ を求めたいなら、メビウス変換すればよい。
その後、$|S|=M$ の箇所のみ $H_S$ を足し合わせれば、答えとなる。

G - Small Multiple 2

• 以下の $2$ つの条件を満たす正の整数 $n$ としてあり得る最小値を求めてください。
  • $n$ は $K$ の倍数である。
  • $n$ の十進法での表記には、部分文字列として $S$ が含まれる。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $T$ は整数。
• $1 \leq T \leq 200$
• $K$ は整数。
• $1 \leq K \leq 10^9$
• $S$ は数字 ('0' - '9') からなる文字列。
• $S$ の先頭の文字は '0' でない。
• $1 \leq |S| \leq 5 \times 10^5$
• すべてのテストケースの $|S|$ の総和は $5 \times 10^5$ 以下である。

制約から、実は $S$ に追加されうる文字列の長さは非常に短い、と気付くところが最初のポイント。

$K \le 10^9$ より、とりあえず $S$ の後ろに9桁を追加して、 000000000～999999999 まで $1$ ずつ増やしていくと、どこかで $\mod{K}$ が $0$ になる接尾辞が存在する。
$n$ の桁数、つまりは「$S$ の前後に追加する文字列長の合計」は小さい方が絶対に数値として小さいので、 $S$ に追加される桁数は多くても9桁である。

前と後ろに付ける文字列をそれぞれ以下のように表す。

• 前に付ける数値（を表す文字列）を $X$、桁数を $d$ とする（leading-zeroなし）
• 後に付ける数値（を表す文字列）を $Y$、桁数を $e$ とする（leading-zeroあり）

ただし便宜上、$X=0$ のとき、$d=0$ として解釈する。同様に、$Y=0$ の時のみ $e=0$ であってもよいものとする。

この時、以下の式を満たすことが、$n$ が $K$ の倍数となる条件となる。（※ここでは、$X,S,Y$ は数値として解釈している）

• $(X \times 10^{|S|} + S) \times 10^e + Y \equiv 0 \mod{K}$ … ①

$d+e \le 9$ より、前か後ろの短い方に付ける文字列の長さは $4$ 以下である。 短い方を $0～9999$ まで全探索し、その時にもう一方の最適値がすぐに求められるのであれば、探索候補は $2 \times 10^4$ 個くらいに絞られる。 計算量も、$10^4$ に「$X$ から $Y$ を求める計算量」（またその逆）をかけたくらいのオーダーで求められ、間に合いそうである。

ただし、$Y$ は $e$ の値によっても結果が違ってきたりなどするので、ちゃんと考えると

• $X$ を $0～10^4$ で仮定
  • → $\mod{K}$ が $0$ になる最小の $e$、その中で最小の $Y$ を求める
• $e$ を $0～4$、$Y$ を $0～10^e$ で仮定
  • → $\mod{K}$ が $0$ になる最小の $X$ を求める

以上を全探索してその中での最小値を求めればよいことになる。これでもオーダーとしては $O(\sqrt{K}) \simeq 10^4$ のままである。

この解法において必要となるのは以下である。

• $F(X)$ : $X$ を仮定したら $(e,Y)$ を求める関数
• $G(e,Y)$ : $(e,Y)$ を仮定したら $X$ を求める関数
• $(X,Y,d,e)$ の大小比較方法（実際に $n$ を作ったときにどちらが小さいか）

$F(X)$ については、式①に $X$ を代入し、 また $e$ を仮定して代入すると、$Y$（として取り得る非負の最小値）が求まる。 $e=0～9$ を小さい方から順に試し、最初に $e \ge |Y|$ となったらそれが最小の $(e,Y)$ となる。
1回当たりの計算量は $O(\log{K})$。

$G(e,Y)$ については、式①に代入すると $X \times p \equiv q$ という形になる（$p,q$ は既知の値）。
この式は、$q$ が $\gcd(p,K)$ の倍数である場合のみ解を持つ。 $g=\gcd(p,K)$ とすると、$X \equiv \dfrac{q}{g} \left ( \dfrac{p}{g} \right )^{-1} \mod{\dfrac{K}{g}}$ となり、求まる。
1回当たりの計算量は、GCDやmod逆数を求めるのに $O(\log{K})$。

任意modの逆数の計算は、pythonなら pow(a, -1, mod) でできる（便利!）が、 そのような関数が無い場合は、ユークリッドの互除法を拡張して求められる。

• MOD 逆数 - 幸せに

$(X,Y,d,e)$ の大小比較についても、意外と一筋縄ではいかない。
実際に $n$ を生成したらオーバーフローするし、文字列のまま比較しようとしても $10000$ 回も $|S| \simeq 5 \times 10^5$ の長さの文字列生成が発生したらTLEとなる。

まずは以下の条件によって残す候補を絞り込む。これらは $(X,Y,d,e)$ のみからほぼ $O(1)$ で判定可能。

• まず $d+e$ が小さい方
• $d+e$ かつ $d$ が同じ中では、$X$ が小さい方
• これらが全て同じ中では $Y$ が小さい方

すると候補は $(d,e)=(0,d+e)～(d+e,0)$ の $d+e+1 \le 10$ 通りにまで抑えられる。
あとは実際に文字列生成して比較しても間に合う。

Python3

from math import gcd


def mod_str(n: str, d: int):
    """ 文字列で与えられる巨大数 n を d で割ったあまり """
    k = 0
    for c in n:
        k = k * 10 + int(c)
        k %= d
    return k


def solve(k, s):
    n = len(s)

    pow10 = [1]
    for _ in range(max(n, 10)):
        pow10.append(pow10[-1] * 10 % k)

    p = pow10[n]
    q = mod_str(s, k)

    # 文字列:    x + s + y  （※ |x|=d, |y|=e とする）
    # 数値modK: (x*p + q) * pow10[e] + y

    def find_y(x):
        base = (x * p + q) % k
        if base == 0:
            return 0, 0
        for e in range(1, 10):
            y = -(base * pow10[e]) % k
            ly = 0 if y == 0 else len(str(y))
            if ly <= e:
                return e, y
        raise NotImplementedError

    def find_x(a, b_base, g, y):
        b = (b_base - y) % k
        if b % g != 0:
            return -1, -1
        k2 = k // g
        x = (b // g) * pow(a // g, -1, k2) % k2
        if x == 0:
            return 0, 0
        return len(str(x)), x

    # 最良評価: 1.d+eが小さい  2.dが同じ中ではxが小さい  で、とりあえず8～9個までに絞り込み、最後に文字列を実際に生成して比較
    best_de = 1 << 60
    best_xy = {}  # best_xy[d]=(x,y)

    for x in range(10000):
        d = 0 if x == 0 else len(str(x))
        e, y = find_y(x)
        # print(f'{d=} {e=} {x=} {y=}')
        de = d + e
        if de > best_de:
            continue
        if de < best_de:
            best_de = de
            best_xy = {d: (x, y)}
        elif d not in best_xy:
            best_xy[d] = (x, y)

    for e in range(5):
        a = p * pow10[e] % k
        b_base = (-q * pow10[e]) % k
        g = gcd(a, k)
        for y in range(10 ** e):
            d, x = find_x(a, b_base, g, y)
            if d == -1:
                continue
            de = d + e
            if de > best_de:
                continue
            if de < best_de:
                best_de = de
                best_xy = {d: (x, y)}
            elif d not in best_xy:
                best_xy[d] = (x, y)
            elif best_xy[d] > (x, y):
                best_xy[d] = (x, y)

    # print(f'{k=} {s=} {best_de=} {best_xy=}')
    cand = set()
    for d, (x, y) in best_xy.items():
        str_x = '' if x == 0 else str(x)
        e = best_de - d
        str_y = '' if e == 0 else str(y).zfill(e)
        cand.add(str_x + s + str_y)
    ans = min(cand)
    return ans


t = int(input())
for _ in range(t):
    k = int(input())
    s = input()
    ans = solve(k, s)
    print(ans)