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

from atcoder.segtree import SegTree


def solve(n, q, queries):
    def merge(a, b):
        return (a[0] + b[0], a[1] + b[1])

    sgt = SegTree(merge, (0, 0), q)
    last_qi_1 = [-1] * n
    last_qi_2 = [-1] * n
    ans = 0
    buf = []
    for qi, (qt, i) in enumerate(queries):
        i -= 1
        if qt == 1:
            lst = last_qi_1[i]
            if lst != -1:
                b, w = sgt.prod(lst, qi)
                ans -= n - w
                sgt.set(lst, (0, 0))
            ans += n
            sgt.set(qi, (1, 0))
            last_qi_1[i] = qi
        else:
            lst = last_qi_2[i]
            if lst != -1:
                b, w = sgt.prod(0, lst)
                ans += b
                sgt.set(lst, (0, 0))
            b, w = sgt.prod(0, qi)
            ans -= b
            sgt.set(qi, (0, 1))
            last_qi_2[i] = qi
        buf.append(ans)
    return buf


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

from collections import defaultdict


def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]


def prime_factorize(x, primes=None):
    """ xを素因数分解、辞書型で返す """
    # primes: sqrt(x)までの素数リスト
    #   省略時は奇数を試し割り（2だけ別処理）
    #   単発なら不要だが、複数のxで行う場合は事前計算した方がよい

    factors = defaultdict(int)
    if primes is None:
        if x & 1 == 0:
            b = (x & -x).bit_length() - 1
            factors[2] = b
            x >>= b
        primes = range(3, x, 2)
    for p in primes:
        if p * p > x:
            break
        if x % p == 0:
            factors[p] = 1
            x //= p
            while x % p == 0:
                factors[p] += 1
                x //= p
    if x != 1:
        factors[x] = 1
    return factors


def get_divisors(pf):
    ppp = sorted(pf.keys())
    k = len(pf)
    divisors = [(1, (0,) * k)]
    for pi, p in enumerate(ppp):
        cnt = pf[p]
        w = len(divisors)
        x = p
        for c in range(cnt):
            for i in range(w):
                a, qqq = divisors[i]
                qqq = list(qqq)
                qqq[pi] += c + 1
                qqq = tuple(qqq)
                divisors.append((a * x, qqq))
            x *= p
    return divisors


def solve(n):
    primes = get_primes(10 ** 5 + 1)
    pf = prime_factorize(n, primes)
    divisors = get_divisors(pf)

    ppp = sorted(pf.keys())
    max_used = tuple(pf[p] for p in ppp)
    MOD = 998244353

    k = len(pf)
    # print(divisors)
    init = {((0,) * k, 0): [1, 0]}
    dp = defaultdict(lambda: [0, 0], init)
    for d, current_use in divisors:
        add_items = []
        for (used, length), (pat, total) in dp.items():
            new_used = []
            ok = True
            for i in range(k):
                nu = used[i] + current_use[i]
                if nu > max_used[i]:
                    ok = False
                    break
                new_used.append(nu)
            if ok == False:
                continue
            new_used = tuple(new_used)
            add_items.append((new_used, length + 1, pat, total + d * pat))

        for used, length, pat, total in add_items:
            item = dp[used, length]
            item[0] += pat
            item[0] %= MOD
            item[1] += total
            item[1] %= MOD

    facts = [1]
    for i in range(1, 100):
        facts.append(facts[-1] * i % MOD)

    ans = 0
    for (used, length), res in dp.items():
        if used == max_used:
            ans += res[1] * facts[length]
    ans %= MOD
    return ans


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

$(0,0.5)$ の範囲の値を“小”、$(0.5,1)$ の範囲の値を“大”とする。いずれの範囲も両端は含まない。
いずれかの $x_i$ が小や大の値を取る最適解が存在したとする。

小の値を取る $x_i$ の集合を $P$、大の値を取る $x_i$ の集合を $Q$ とする。

$|P| \gt |Q|$ なら、小の値を一律 $\epsilon$ 増やし、大の値を一律 $\epsilon$ 減らすことができる。 この操作で $\sum x_i$ を大きくできるので、最適解であることに矛盾する。

$|P| \lt |Q|$ の場合も、大を $\epsilon$ 増やし、小を $\epsilon$ 減らすことで同じことが言える。

よって $|P|=|Q|$ となる。 この時、上と同様の操作で $\epsilon$ を適切な値にすることで、$\sum x_i$ を保ったまま、$P,Q$ の中で一番端に近いやつを $0,0.5,1$ のいずれかにすることができ、$|P|+|Q|$ を減らすことができる。

これを繰り返すと、$\sum x_i$ を保ったまま $|P|=|Q|=0$ の解にすることができる。

倍加した二部グラフでの整数解を、$Y_{1},...,Y_{N},Z_{1},...,Z_{N}$ とする。
$Y$ は $A$ 側頂点、$Z$ は $B$ 側頂点に割り当てる値であり、$Y_i,Z_i \in \{0,1\}$ の整数値を取る。 辺制約は二部グラフの構築の部分の説明の通り。

また、二部グラフでのLP緩和問題の解を $y_{1},...,y_{N},z_{1},...,z_{N}$ とする。
$0 \le y_i,z_i \le 1$ の実数値を取る。辺制約は同じ。

この時、元の問題で最大値を達成する $\sum x_i$ は、$\dfrac{\sum Y_i + \sum Z_i}{2}$ として与えられることを示す。

補題1:

• 元のLP緩和問題で、最適解を与える $x=(x_1,...,x_N)$ の集合を $P(G)$、その $\sum x_i$ の値を $LP(G)$ とする。
• 二部グラフのLP緩和問題で最適解を与える $(y,z)$ の集合を $P(H)$、その $\sum y_i + \sum z_i$ を $LP(H)$ とする。
• この時、$LP(H)=2LP(G)$ である。

任意の $x \in P(G)$ につき、$y=z=x$ とした $(y,z)$ は二部グラフ上の制約（辺 $(u,v)$ に対し $y_u+z_v \le 1, y_v+z_u \le 1$）を満たす。この時、$\sum y_i + \sum z_i = 2LP(G)$ である。 もしかするとこれ以上を達成する $(y,z)$ が存在するかもしれないが、少なくとも $LP(H) \ge 2LP(G)$ であることは言える。

また、任意の $(y,z) \in P(H)$ につき、$x_i=\dfrac{y_i+z_i}{2}$ とした $x_i$ は、元のグラフでの制約を満たす。 （二部グラフの制約より $y_u+z_u+y_v+z_v \le 2$ なので、両辺を2で割ると導ける）
もしかするとこれ以上を達成する $x$ が存在するかもしれないが、少なくとも $LP(H) \le 2LP(G)$ であることは言える。

両者を合わせて、$LP(H)=2LP(G)$ が言える。

補題2:

• 二部グラフのLP緩和解 $LP(H)$ は、整数解 $\alpha(H)$ と一致する。

直感的には、二部グラフなら、2つに分かれたグループのうち サイズの大きい方に“1”、小さい方に“0”を割り当てるのが、実数を取れるかどうかに関係なく最適だよね、ということ。
ちゃんと証明するなら、半整数性を示した時のように「最適解に0でも1でもない値が含まれたら、それを0または1まで動かして損しない」ことを言えばよい。

以上で $LP(G)=\dfrac{1}{2}\alpha(H)$ が示せた。

もし、具体的な $x_i$ の一例も必要な場合は、$x_i=\dfrac{Y_i+Z_i}{2}$ とすることで求めることができる。

from atcoder.maxflow import MFGraph


def solve(n, m, edges):
    dnc = MFGraph(n * 2 + 2)
    s = n * 2
    t = s + 1
    for i in range(n):
        dnc.add_edge(s, i, 1)
        dnc.add_edge(i + n, t, 1)
    for u, v in edges:
        u -= 1
        v -= 1
        dnc.add_edge(u, v + n, 1)
        dnc.add_edge(v, u + n, 1)
    flow = dnc.flow(s, t)
    mis_size = n * 2 - flow
    ans = mis_size * 1013
    return ans


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