米哈游 2026-9-6 笔试真题 - 通用岗

## 道具分配 - 分类讨论（构造 + 奇偶不变量）


def can_finish(n, s, t, a):
    """判断能否恰好用 t 次操作把初始局面变成目标局面 a。"""
    # 操作只是搬运，道具总数守恒，所以总数对不上直接否定
    if sum(a) != s:
        return False
    # 没有道具可搬，或只有一个格子无处可搬，一步都动不了
    if s == 0 or n == 1:
        return t == 0
    # need 是必须离开 1 号格子的道具数，也就是达成目标所需的最少操作次数
    need = s - a[0]
    if n == 2:
        # 只有两格时每次操作都在两格之间来回，1 号格子的件数每步变化 1，
        # 奇偶性被锁死，因此总步数必须与 need 同奇偶
        return t >= need and (t - need) % 2 == 0
    if need >= 1:
        # 三格以上时可以让某件要搬走的道具绕第三个格子多走一步，
        # 于是奇偶不再是障碍，只要步数够用即可
        return t >= need
    # need == 0 说明目标就是初始局面：一步必然打破局面回不来，两步可以来回一趟
    return t == 0 or t >= 2


## 读入规模与目标局面，t 最大到 1e18，Python 整数天然不会溢出
n, s, t = map(int, input().split())
a = list(map(int, input().split()))
print("Yes" if can_finish(n, s, t, a) else "No")

## 三进制翻转查询 - 线段树（区间合并）+ 三进制位权闭式
MOD = 998244353


## 把一个整数编码成 (三进制位数, 这一段单独解读出的数值)
## 推导：串 s_0..s_{L-1} 先互换 0/2（即 s -> 2-s）再首尾翻转，按三进制求值展开后
## 正好等于 sum_j (2 - s_j) * 3^j，也就是「左边第 j 位的权重是 3^j」。
## 有了这个闭式，每个元素就能脱离上下文单独预处理。
def encode(v):
    if v == 0:
        digits = [0]                      # 0 写成一位的 0，除法循环给不出这一位
    else:
        digits = []
        while v > 0:
            digits.append(v % 3)
            v //= 3
        digits.reverse()                  # 反转后 digits[j] 才是从左数第 j 位
    val = 0
    for j in range(len(digits) - 1, -1, -1):
        val = val * 3 + (2 - digits[j])   # 霍纳法从高 j 往低 j 累，等价于 sum (2-d_j)*3^j
    return len(digits), val % MOD


m, q = map(int, input().split())
v = list(map(int, input().split()))

## 1e9 的三进制最多 19 位，拼接后总长不超过 19*m，pow3 一次备齐，合并时 O(1) 取用
pow3 = [1] * (19 * m + 2)
for i in range(1, len(pow3)):
    pow3[i] = pow3[i - 1] * 3 % MOD

## 迭代式线段树：叶子层补齐到 2 的幂，避免递归写法在深度上冒风险
size = 1
while size < m:
    size <<= 1
t_len = [0] * (2 * size)
t_val = [0] * (2 * size)
for i in range(m):
    t_len[size + i], t_val[size + i] = encode(v[i])
## 自底向上建树。合并两段时右段整体向左平移了 A.len 位，所以要乘 3^{A.len}
for i in range(size - 1, 0, -1):
    t_len[i] = t_len[2 * i] + t_len[2 * i + 1]
    t_val[i] = (t_val[2 * i] + t_val[2 * i + 1] * pow3[t_len[2 * i]]) % MOD

for _ in range(q):
    op, a, b = map(int, input().split())
    if op == 2:
        # 单点修改：改掉叶子后一路向上重算，合并顺序不能交换（左右段权重不对称）
        i = size + a - 1
        t_len[i], t_val[i] = encode(b)
        i >>= 1
        while i >= 1:
            t_len[i] = t_len[2 * i] + t_len[2 * i + 1]
            t_val[i] = (t_val[2 * i] + t_val[2 * i + 1] * pow3[t_len[2 * i]]) % MOD
            i >>= 1
    else:
        # 区间查询：自底向上时命中的块，左边界给的是从左往右、右边界给的是从右往左，
        # 所以要分成左右两个累加器，最后再合并一次，才能保证拼接顺序与下标顺序一致
        left_len, left_val = 0, 0
        right_len, right_val = 0, 0
        lo = size + a - 1
        hi = size + b
        while lo < hi:
            if lo & 1:
                left_val = (left_val + t_val[lo] * pow3[left_len]) % MOD
                left_len += t_len[lo]
                lo += 1
            if hi & 1:
                hi -= 1
                right_val = (t_val[hi] + right_val * pow3[t_len[hi]]) % MOD
                right_len += t_len[hi]
            lo >>= 1
            hi >>= 1
        print((left_val + right_val * pow3[left_len]) % MOD)