AtCoder Regular Contest++ 233 A問題メモ

$3$ 個の構成方法は、「$X$ から1個、$Y$ から2個」か「$Y$ から3個」のいずれかである。 （$X$ から2個以上取ると和が $N$ を超えるので）

同様に、$k$ 個の構成方法は「(a) $X$ から1個、$Y$ から $k-1$ 個」か「(b) $Y$ から $k$ 個」のいずれかである。

$k = 4$ かつ (a) の時、$Y$ 側から取る小さい方を $a,b,c$ とする。

U  ... ×N-a ... ×N-b ... ×N-c ... ×N-a-b ... ○N-a-b-c ...
L  ... ○ a  ... ○ b  ... ○ c  ... ○ a+b  ... × a+b+c  ...

この時、$A$ に $N-a-b$ が含まれていると $3$ 個が構成できてしまうので、$N-a-b$ は含まれていない。
つまり、$A$ には $a+b$ が含まれていることになる。

すると、$(a+b)+(c)+(N-a-b-c)$ が $3$ 個で構成できてしまう。
$a+b=c$ の時はこの限りではないが、その場合は $a+c$ などで同じことが言える。

$k=4$ かつ (b) の時も、(a) との違いは $N-a-b-c$ が $L$ 側にあるだけである。 $a,b,c,N-a-b-c$ がこの順に大きくなる前提で、$a+b \lt \frac{N}{2}$ より、 $N-a-b$ は $U$ 側、$a+b$ は $L$ 側であり、同様の議論が成り立つ。

$k \gt 4$ の時でも同様に $k-1$ が構成できてしまうことから、最小に矛盾する。

これだと(b)かつ $a+b=c$ となってしまう場合に漏れがありそう。

import sys


class NttConvolution:
    """
    NTT (Number Theoretic Transform) for Codon.
    MOD = 998244353 = 119 * 2^23 + 1, primitive root = 3.
    Maximum transform length: 2^23 = 8388608.

    Usage:
        ntt = NttConvolution()
        c = ntt.convolution(a, b)
        c = ntt.convolution_all([a, b, c, d])
        ntt.ntt(a)   # in-place forward transform
        ntt.intt(a)  # in-place inverse transform

    library: https://github.com/ikatakos/atcoder-lib-ai-assisted
    """

    _roots: list[int]
    _inv_roots: list[int]

    def __init__(self) -> None:
        _M = 998244353
        _G = 3
        _LOG2 = 23
        roots = [0] * (_LOG2 + 1)
        inv_roots = [0] * (_LOG2 + 1)
        roots[_LOG2] = NttConvolution._pow_mod(_G, (_M - 1) // (1 << _LOG2))
        inv_roots[_LOG2] = NttConvolution._pow_mod(roots[_LOG2], _M - 2)
        for i in range(_LOG2 - 1, -1, -1):
            roots[i] = roots[i + 1] * roots[i + 1] % _M
            inv_roots[i] = inv_roots[i + 1] * inv_roots[i + 1] % _M
        self._roots = roots
        self._inv_roots = inv_roots

    @staticmethod
    def _pow_mod(base: int, exp: int) -> int:
        _M = 998244353
        result = 1
        base %= _M
        while exp > 0:
            if exp & 1:
                result = result * base % _M
            exp >>= 1
            base = base * base % _M
        return result

    @staticmethod
    def _bit_length(n: int) -> int:
        k = 0
        while n > 0:
            k += 1
            n >>= 1
        return k

    def _transform(self, a: list[int], invert: bool) -> None:
        _M = 998244353
        n = len(a)
        k = NttConvolution._bit_length(n) - 1
        table = self._inv_roots if invert else self._roots

        j = 0
        for i in range(1, n):
            bit = n >> 1
            while j & bit:
                j ^= bit
                bit >>= 1
            j ^= bit
            if i < j:
                a[i], a[j] = a[j], a[i]

        length = 1
        for s in range(k):
            length <<= 1
            half = length >> 1
            w = table[s + 1]
            i = 0
            while i < n:
                wn = 1
                for t in range(half):
                    u = a[i + t]
                    v = a[i + t + half] * wn % _M
                    a[i + t] = (u + v) % _M
                    a[i + t + half] = (u - v + _M) % _M
                    wn = wn * w % _M
                i += length

        if invert:
            inv_n = NttConvolution._pow_mod(n, _M - 2)
            for i in range(n):
                a[i] = a[i] * inv_n % _M

    def ntt(self, a: list[int]) -> None:
        self._transform(a, False)

    def intt(self, a: list[int]) -> None:
        self._transform(a, True)

    def convolution(self, a: list[int], b: list[int]) -> list[int]:
        _M = 998244353
        n = len(a)
        m = len(b)
        if n == 0 or m == 0:
            return []
        result_len = n + m - 1

        if min(n, m) <= 60:
            c = [0] * result_len
            if n < m:
                for i in range(n):
                    ai = a[i]
                    if ai == 0:
                        continue
                    for j in range(m):
                        c[i + j] = (c[i + j] + ai * b[j]) % _M
            else:
                for j in range(m):
                    bj = b[j]
                    if bj == 0:
                        continue
                    for i in range(n):
                        c[i + j] = (c[i + j] + a[i] * bj) % _M
            return c

        sz = 1
        while sz < result_len:
            sz <<= 1

        fa = [0] * sz
        fb = [0] * sz
        for i in range(n):
            fa[i] = a[i] % _M
        for i in range(m):
            fb[i] = b[i] % _M

        self._transform(fa, False)
        self._transform(fb, False)

        for i in range(sz):
            fa[i] = fa[i] * fb[i] % _M

        self._transform(fa, True)
        return fa[:result_len]

    def convolution_all(self, polys: list[list[int]]) -> list[int]:
        from collections import deque
        if len(polys) == 0:
            return [1]
        q: deque[list[int]] = deque(polys)
        while len(q) > 1:
            a = q.popleft()
            b = q.popleft()
            q.append(self.convolution(a, b))
        return q[0]


ntt = NttConvolution()


def solve():
    def parse_response(res):
        if res == '-1':
            sys.exit()
        elif res == 'Yes':
            return True
        elif res == 'No':
            return False

    n = int(input())
    h = n // 2
    exists = [0] * n

    if n % 2 == 0:
        print(f'? {h}', flush=True)
        if parse_response(input()):
            exists[h] = 1
        else:
            print('! 2', flush=True)
            return True

    count_o = 0
    count_x = 0
    for i in range(n - 1, h, -1):
        print(f'? {i}', flush=True)
        if parse_response(input()):
            exists[i] = 1
            count_o += 1
        else:
            count_x += 1

    if count_o <= count_x:
        for i in range(n - 1, h, -1):
            if exists[i] == 1:
                j = n - i
                print(f'? {j}', flush=True)
                if parse_response(input()):
                    print('! 2', flush=True)
                    return True
    else:
        for i in range(n - 1, h, -1):
            if exists[i] == 0:
                j = n - i
                print(f'? {j}', flush=True)
                if not parse_response(input()):
                    print('! 2', flush=True)
                    return True

    lowers = set()
    for i in range(n - 1, h, -1):
        if exists[i] == 0:
            exists[n - i] = 1
            lowers.add(n - i)
    aaa = exists[:h + (n % 2)]
    use2 = ntt.convolution(aaa, aaa)
    for i in lowers:
        use2[i * 2] -= 1
    for i in range(n - 1, h - (1 - (n % 2)), -1):
        if exists[i] == 1 and use2[n - i] > 0:
            print('! 3', flush=True)
            return True
    for i in range(2, h):
        if exists[i] == 1:
            jk = n - i
            cnt = use2[jk]
            if n - i - i in lowers and i * 3 != n:
                cnt -= 2
            if cnt > 0:
                print('! 3', flush=True)
                return True
    print('! -1', flush=True)
    return True


if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()