AtCoder Beginner Contest 356 D,E,F,G問題メモ

def solve(n, m):
    MOD = 998244353
    ans = 0
    for d in range(60):
        b = 1 << d
        if m & b == 0:
            continue

        mask = b - 1
        ans += (n >> d + 1) * b

        if n & b > 0:
            ans += (n & mask) + 1
        ans %= MOD

    return ans


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

from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
a_max = max(aaa)
cnt = [0] * (a_max + 1)
for a in aaa:
    cnt[a] += 1
acc = list(accumulate(cnt))

ans = 0
for a in range(1, a_max + 1):

    if cnt[a] == 0:
        continue

    c = cnt[a]
    r = int(a ** 0.5)
    tmp = 0
    for d in range(1, r + 1):
        k = a // d
        tmp += acc[k] + k * cnt[d]
    tmp -= acc[r] * r

    ans += tmp * c
    ans -= c * (c + 1) // 2

print(ans)

from sortedcontainers import SortedSet

q, k = map(int, input().split())
INF = 1 << 62
total = SortedSet([-INF, INF])
left = SortedSet([-INF, INF])
right = SortedSet([-INF, INF])
buf = []
for _ in range(q):
    op, x = map(int, input().split())
    if op == 1:
        i = total.bisect_left(x)
        if total[i] == x:
            l = total[i - 1]
            r = total[i + 1]
            total.remove(x)
            if r - l <= k:
                pass
            elif x - l > k:
                if r - x > k:
                    left.remove(x)
                    right.remove(x)
                else:
                    left.remove(x)
                    left.add(r)
            elif r - x > k:
                right.remove(x)
                right.add(l)
            else:
                left.add(r)
                right.add(l)
        else:
            l = total[i - 1]
            r = total[i]
            total.add(x)
            if r - l <= k:
                pass
            elif x - l > k:
                if r - x > k:
                    left.add(x)
                    right.add(x)
                else:
                    left.remove(r)
                    left.add(x)
            elif r - x > k:
                right.remove(l)
                right.add(x)
            else:
                left.remove(r)
                right.remove(l)
    else:
        li = left.bisect_right(x) - 1
        ri = right.bisect_left(x)
        l = left[li]
        r = right[ri]
        tli = total.index(l)
        tri = total.index(r)
        ans = tri - tli + 1
        buf.append(ans)

print('\n'.join(map(str, buf)))

from collections import defaultdict


def ccw(ax, ay, bx, by, cx, cy):
    """
        C         :1
    A------>B  C  :0
        C         :-1
    """
    dx1 = bx - ax
    dy1 = by - ay
    dx2 = cx - ax
    dy2 = cy - ay
    if dy1 * dx2 > dy2 * dx1:
        return -1
    if dx1 * dy2 > dy1 * dx2:
        return 1
    if dx1 * dx2 < 0 or dy1 * dy2 < 0:
        return 1
    if dx1 * dx1 + dy1 * dy1 < dx2 * dx2 + dy2 * dy2:
        return -1
    return 0


def intersection(x1, y1, x2, y2, x3, y3):
    """
    2つの直線が交わる座標を求める関数

    引数:
      x1, y1: 1つ目の直線の1つ目の点の座標
      x2, y2: 1つ目の直線の2つ目の点の座標
      x3, y3: 2つ目の直線の1つ目の点の座標 (原点(0, 0))
    返り値:
      交点の座標 (x, y) のタプル。交差しない場合は (None, None) を返す。
    """

    # 1つ目の直線の傾きと切片を求める
    dx1 = x2 - x1
    dy1 = y2 - y1
    if dx1 == 0:
        slope1 = None
    else:
        slope1 = (y2 - y1) / (x2 - x1)
    intercept1 = y1 - slope1 * x1

    # 2つ目の直線の傾きと切片を求める
    dx2 = x3
    dy2 = y3
    if dx2 == 0:
        slope2 = None
    else:
        slope2 = y3 / x3
    intercept2 = 0

    # 2つの直線が平行かどうか判定する
    if slope1 == slope2:
        return None, None

    # 交点のx座標を求める
    if slope1 is None:
        x = x3
    elif slope2 is None:
        x = x1
    else:
        x = (intercept2 - intercept1) / (slope1 - slope2)

    # 交点のy座標を求める
    if slope1 is None:
        y = slope2 * x + y3
    elif slope2 is None:
        y = slope1 * x + y1
    else:
        y = slope1 * x + intercept1

    # 交点の座標を返す
    return x, y


n = int(input())
points = defaultdict(int)
for _ in range(n):
    a, b = map(int, input().split())
    points[a] = max(points[a], b)

uch = [(0, 0)]  # upper convex hull
for a in sorted(points.keys()):
    b = points[a]
    if uch[-1][1] >= b:
        continue
    while len(uch) >= 2:
        if ccw(uch[-2][0], uch[-2][1], uch[-1][0], uch[-1][1], a, b) == 1:
            uch.pop()
        else:
            break
    uch.append((a, b))

uch.pop(0)

pa, pb = uch[0]
qa, qb = uch[-1]
m = len(uch)

q = int(input())
buf = []
for _ in range(q):
    c, d = map(int, input().split())
    if qb * c >= qa * d:
        buf.append(d / qb)
        continue
    if pb * c < pa * d:
        buf.append(-1)
        continue
    l = 0
    r = m
    while l + 1 < r:
        mid = (l + r) // 2
        ra, rb = uch[mid]
        if rb * c > ra * d:
            l = mid
        else:
            r = mid
    x, y = intersection(uch[l][0], uch[l][1], uch[r][0], uch[r][1], c, d)
    buf.append(d / y)

print('\n'.join(map(str, buf)))