JIJプログラミングコンテスト 2026（AtCoder Beginner Contest 476）F,G問題メモ

from itertools import accumulate


def solve(n, m, aaa, bbb):
    populations = [[a * b % m for b in bbb] for a in aaa]
    acc_fwd = [list(accumulate(row)) for row in populations]
    acc_bwd = []
    for row in populations:
        acc_row = list(accumulate(reversed(row)))
        acc_row.reverse()
        acc_bwd.append(acc_row)

    acc2_fwd = [list(accumulate(row)) for row in acc_fwd]
    acc2_bwd = []
    for row in acc_bwd:
        tmp = list(accumulate(reversed(row)))
        tmp.reverse()
        acc2_bwd.append(tmp)

    from_ul = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp = 0
            if j == 0:
                tmp = acc_fwd[i][0]
            else:
                if i > 0:
                    tmp += from_ul[i - 1][j - 1]
                tmp += acc2_fwd[i][j - 1] + acc_fwd[i][j]
            from_ul[i][j] = tmp
    from_dl = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(n):
            tmp = 0
            if j == 0:
                tmp = acc_fwd[i][0]
            else:
                if i < n - 1:
                    tmp += from_dl[i + 1][j - 1]
                tmp += acc2_fwd[i][j - 1] + acc_fwd[i][j]
            from_dl[i][j] = tmp
    from_ur = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n - 1, -1, -1):
            tmp = 0
            if j == n - 1:
                tmp = acc_bwd[i][j]
            else:
                if i > 0:
                    tmp += from_ur[i - 1][j + 1]
                tmp += acc2_bwd[i][j + 1] + acc_bwd[i][j]
            from_ur[i][j] = tmp
    from_dr = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            tmp = 0
            if j == n - 1:
                tmp = acc_bwd[i][j]
            else:
                if i < n - 1:
                    tmp += from_dr[i + 1][j + 1]
                tmp += acc2_bwd[i][j + 1] + acc_bwd[i][j]
            from_dr[i][j] = tmp

    ans = 0
    for i in range(n):
        base = 0
        for i2 in range(n):
            base += acc_fwd[i2][-1] * abs(i - i2)
        for j in range(n):
            tmp = base
            if j > 0:
                tmp += from_ul[i][j - 1] + from_dl[i][j - 1] - acc2_fwd[i][j - 1]
            if j < n - 1:
                tmp += from_ur[i][j + 1] + from_dr[i][j + 1] - acc2_bwd[i][j + 1]
            tmp += i * n + j
            ans ^= tmp
    return ans


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

$[L,R)$ を1つ以上の区間 $S=(S_{n_1,k_1},S_{n_2,k_2},...,S_{n_m,k_m})$ に分割したとする。
漏れなく分割しているので、$n_{i+1}=n_{i}+2^{k_{i}}$ となる。

証明したいのは、以下となる。

• $[L,R)$ の範囲の整数のpopcountからなる数列全体の最長広義減少部分列を1つ取り、それに採用された（popcountを取る前の）元の整数の集合を $T$ とする。
• この時、以下を満たすような $T$ が必ず存在する。
  • いずれの区間 $S_{n_i,k_i} \in S$ においても、区間内の整数 $t$ に対して、「$t \in T$ なら、$\operatorname{popcount}(t)$ は一定値である」が成り立つ。（※異なる区間では異なってよい）

まず、1つのブロック $S_{n,k}$ から取る減少部分列の長さは、以下が必要条件となる。

• 整数を bit の集合として見た場合、どの2つも包含関係にない

例えば $10$（1010, popcount=2）と $14$（1110, popcount=3）のように包含関係にあったら、 数字が大きい方がpopcountも大きいに決まっているので、減少部分列とはならないからである。

どの2つも包含関係にない冪集合を、「反鎖」と呼ぶ。

• Sperner の定理 - AtCoderInfo

反鎖に関連する定理や公式として、「Spernerの定理」や「LYM不等式」などがある。
これらを使うと、各 $S_{n,k}$ から採用できる個数に上限を与えられる。 その上限を達成できることは簡単に示せ、その方法こそが「popcountが全て同じ値を採用すること」なので、これを使って証明していく。

Sperner の定理とは、「$x$ 元集合の冪集合から選べる反鎖の最大サイズは $\dbinom{x}{\lfloor x/2 \rfloor}$」ということを示す定理である。今回の場合、$S_{n,k}$ は $k$ 元集合と見なせるので、そこから反鎖として採用できる数は $M=\dbinom{k}{\lfloor k/2 \rfloor}$ 個を超えない。逆に、$M$ 個は実際に採用できる。特定の個数の bit が立った整数を全て採用すればよいからである。

したがって、もし仮に、$(S_{n_1,k_1},S_{n_2,k_2},...)$ に分割した各範囲それぞれからの採用数が最大となるように取った結果、 全体を通しても単調減少を達成していれば、それが最大となる。

だが、必ずしも達成できるとは限らない。$S_{n_{i-1},k_{i-1}}$ からは “3” を取った方がよいのに、 $S_{n_i,k_i}$ からは “4” を取るのが最大となるケースもあり得るからだ。

そこで、Spernerの定理の証明にも使われる「LYM不等式」を考慮する。

• $\displaystyle \sum_{c=0}^{k}\frac{反鎖に採用したサイズ c の集合の個数}{\binom{k}{c}} \le 1$

言い換えると、

• サイズ $c$ の集合を1つ反鎖に採用するのにコスト $\dfrac{1}{\binom{k}{c}}$ かかります。
• 反鎖を維持しつつ、コストが $1$ を超える方法はあり得ません。

という主張となる。

（話が戻るが、これを使うとSpernerの定理も簡単に導ける。 サイズ $c=k/2$ であるものが一番コストが安くなるので、それを全て採用するのが最適）

今回、前後の列からの制約の上で $c=k/2$ が使えなくても、制約内でなるべく $k/2$ に近い $c$ が一番コストが安くなり、 それを全て採用するのが最適とわかる。

def solve(queries):
    ncr = [[0] * 61 for _ in range(61)]
    ncr[0][0] = 1
    for i in range(1, 61):
        for j in range(61):
            ncr[i][j] = ncr[i - 1][j - 1] + ncr[i - 1][j]

    def solve2(l, r):
        if l + 1 == r:
            return 1
        if l == 0:
            l = 1
        lbl = l.bit_length() - 1
        rbl = r.bit_length() - 1
        if lbl == rbl:
            x = l ^ r
            mask = (1 << x.bit_length()) - 1
            return solve2(l & mask, r & mask)
        m = rbl + 1
        mlb = (l & -l).bit_length() - 1
        rem = l.bit_count() - 1
        row = [0] * rem + ncr[mlb][:m - rem]
        grid = [row]
        for i in range(mlb + 1, lbl):
            if (1 << i) & l:
                rem -= 1
                continue
            row = [0] * rem + ncr[i][:m - rem]
            grid.append(row)
        for i in range(lbl + 1, rbl):
            grid.append(ncr[i][:m])
        t = r ^ (1 << rbl)
        rem = 0
        while t > 0:
            tbl = t.bit_length() - 1
            row = [0] * rem + ncr[tbl][:m - rem]
            grid.append(row)
            rem += 1
            t ^= 1 << tbl
        n = len(grid)
        prev_row = grid[0][:]
        for j in range(m - 2, -1, -1):
            prev_row[j] = max(prev_row[j], prev_row[j + 1])
        for i in range(1, n):
            row = [0] * m
            row[-1] = prev_row[-1] + grid[i][-1]
            for j in range(m - 2, -1, -1):
                row[j] = max(prev_row[j] + grid[i][j], row[j + 1])
            prev_row = row
        ans = max(prev_row)
        return ans

    buf = []
    for l, r in queries:
        ans = solve2(l, r + 1)
        buf.append(ans)
    return buf


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