ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）F,G問題メモ

n, m, k = map(int, input().split())
vvv = {0}
extra_edges = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    vvv.add(x)
    vvv.add(y)
    extra_edges.append((x, y))
nn = len(vvv)
vvv = sorted(vvv)
rev = {v: i for i, v in enumerate(vvv)}
links = [[] for _ in range(nn)]
to_next = [0] * nn
for x, y in extra_edges:
    links[rev[x]].append((rev[y], 1))
for i in range(nn - 1):
    links[i].append((i + 1, vvv[i + 1] - vvv[i]))
    to_next[i] = vvv[i + 1] - vvv[i]
links[nn - 1].append((0, n - vvv[nn - 1]))
to_next[nn - 1] = n - vvv[nn - 1]

dp = [[0] * nn for _ in range(k + 1)]
dp[0][0] = 1
MOD = 998244353
for i in range(k):
    for j in range(nn):
        dp_ij = dp[i][j]
        if dp_ij == 0:
            continue
        for v, c in links[j]:
            if i + c > k:
                continue
            dp[i + c][v] += dp_ij
            dp[i + c][v] %= MOD

ans = 0
for i in range(nn):
    for j in range(to_next[i]):
        if j > k:
            break
        ans += dp[k - j][i]
        ans %= MOD
print(ans)

from functools import cmp_to_key
from math import gcd


def floor_sum(n, m, a, b):
    """
    i = 0..n-1 につき、(ai + b) // m の和を計算する

    https://rsk0315.hatenablog.com/entry/2020/12/13/231307
    """
    if n <= 0:
        return 0

    result = 0
    if a < 0:
        # a±m は45度の ◢ or ◥ の分の足し引きで調整できる。
        a2 = a % m
        result -= n * (n - 1) // 2 * ((a2 - a) // m)
        a = a2
    if b < 0:
        # b±m は n×m の矩形の足し引きで調整できる。
        b2 = b % m
        result -= n * ((b2 - b) // m)
        b = b2

    while n:
        if a >= m:
            d, a = divmod(a, m)
            result += n * (n - 1) // 2 * d
        if b >= m:
            d, b = divmod(b, m)
            result += n * d
        d, mod = divmod(a * (n - 1) + b, m)
        result += d
        n = d
        m, a = a, m
        b = mod
    return result


def count_grid_points_on_line(a, b, c, l, r):
    """ y=(-a/b)x+(c/b) が通る格子点の、l<=x<r の範囲での個数 """
    g = gcd(a, b)
    if c % g != 0:
        return 0
    a //= g
    b //= g
    c //= g
    x0 = c * pow(a, -1, b) % b
    return (r - x0 - 1) // b - (l - x0 - 1) // b


def solve(n, lines):
    def cmp_func(abc1, abc2):
        l = -abc1[0] * abc2[1]
        r = -abc1[1] * abc2[0]
        if l == r:
            return 0
        if l < r:
            return -1
        else:
            return 1

    # 傾きが同じやつがあるとCHTでちょっと面倒なので、切片が一番下のやつのみ残す
    use_lines = {}
    for a, b, c in lines:
        g = gcd(a, b)
        key = (a // g, b // g)
        if key in use_lines:
            a1, b1, c1 = use_lines[key]
            if b * c1 > b1 * c:
                use_lines[key] = (a, b, c)
        else:
            use_lines[key] = (a, b, c)
    lines = sorted(use_lines.values(), key=cmp_to_key(cmp_func), reverse=True)
    # ConvexHullTrick
    INF = 1 << 30
    stack = [(-INF * INF, 1, -INF, -INF)]  # (a, b, c, d) -> 傾き -a/b, 切片 c/b の直線が、現状 x >= d 以降で最小
    for a, b, c in lines:
        while True:
            a0, b0, c0, d0 = stack[-1]
            # (a,b,c) が、x=d0 で (a0,b0,c0) より下なら、(a0,b0,c0) は意味が無い
            if -a * b0 * d0 + c * b0 <= -a0 * b * d0 + c0 * b:
                stack.pop()
            else:
                cb = c0 * b - c * b0
                ab = a0 * b - a * b0
                if cb < 0:
                    cb *= -1
                    ab *= -1
                d1 = (cb - 1) // ab + 1
                stack.append((a, b, c, d1))
                break
    # 最後の直線の分を余裕を持って追加。
    stack.append((0, 0, 0, 1 << 60))
    # 格子点の個数を floor_sum で数える
    ans = 0
    for i in range(1, len(stack) - 1):
        a, b, c, d0 = stack[i]
        _, _, _, d1 = stack[i + 1]
        # 直線の開始点の時点で y<=0 なら以降は不要
        if -a * d0 + c <= 0:
            break
        # x軸をまたぐ場合は、x軸との交点まで（次のループでbreak）
        d1 = min(d1, (c - 1) // a + 1)
        ans += floor_sum(d1, b, -a, c) - floor_sum(d0, b, -a, c)
        # 直線の上にある格子点を除く
        ans -= count_grid_points_on_line(a, b, c, d0, d1)
    return ans


t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    lines = [tuple(map(int, input().split())) for _ in range(n)]
    ans = solve(n, lines)
    buf.append(ans)

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