2026-04-11 某外卖厂暑期笔试复盘

第一题：恰好选 x 组，使和为奇数

题目大意

多组数据。每组给定 $n$ 、 $x$ 和长度为 $n$ 的数组 $a$ ，按下标两两分组： $(a_0,a_1)$ 、 $(a_2,a_3)$ ，依次往后。如果 $n$ 是奇数，最后一个数单独成组。

一共有 $G=\lceil n/2\rceil$ 组， $1\le x\le G$ 。恰好选出 $x$ 组，每组选一个数，问这些数的和能不能是奇数。能就输出 Yes，否则输出 No。

思路分析

只需要看奇偶，把每组分成三类：

两个数一奇一偶，可以自由选奇数或偶数。
两个数都是奇数，或单独一个奇数，只能贡献奇数。
两个数都是偶数，或单独一个偶数，只能贡献偶数。

只要有一组一奇一偶，答案就是 Yes。先把它选上，再从其余组里任意选 $x-1$ 组。最后通过这一组选奇数还是偶数，就能把总和调成奇数。

如果没有这样的组，设只能贡献奇数的组有 $O$ 个，只能贡献偶数的组有 $E$ 个。选出的奇数组数 $t$ 必须满足

\max(0,x-E)\le t\le\min(x,O)

这个区间里的每个整数都能取到。只要里面有奇数就行：区间只有一个整数时判它的奇偶；有至少两个整数时，一定包含奇数。

单独成组的最后一个数也要算进去。这里选的是每组中的一个数，不是把整组求和。

每组时间复杂度 $O(n)$ ，下面的写法保留分组，额外空间 $O(n)$ 。

参考代码

def can_odd(a, x):
    n = len(a)
    groups = []
    for i in range(0, n, 2):
        if i + 1 < n:
            groups.append((a[i] % 2, a[i + 1] % 2))
        else:
            groups.append((a[i] % 2,))          # 单元素组

    G = len(groups)
    if x < 1 or x > G:
        return False

    # 灵活组：二元组且两数奇偶不同
    if any(len(g) == 2 and g[0] != g[1] for g in groups):
        return True

    # 贡献固定的组：两个都是奇数，或单元素为奇数
    odd_g = 0
    for g in groups:
        if g[0] == 1:
            odd_g += 1
    even_g = G - odd_g

    lo = max(0, x - even_g)
    hi = min(x, odd_g)
    if lo > hi:
        return False
    if lo == hi:
        return lo % 2 == 1
    return True

第二题：连续窗口和与 m 周期数组计数

题目大意

给定 $n,v,m,k$ ，数组长度为 $n$ ，每个元素在 $1\dots v$ 。统计方案数，答案对 $10^9+7$ 取模。参数范围大致为 $n,v,m\le2\times10^5$ ， $k\le10^9$ ，并且 $k\ge m$ 。

下面讨论的计数条件是：至少有一个长度为 $m$ 的连续子数组，其和不等于 $k$ 。

思路分析

先数补集：每个长度为 $m$ 的连续子数组，其和都等于 $k$ 。

这是我当时想到的方向。相邻两个窗口的和相等，减一下就有

a_{i+m}=a_i

所以在 $n\ge m$ 时，整个数组由前 $m$ 项确定。只要这 $m$ 项的和为 $k$ ，后面按周期重复，就能得到补集里的一个数组。问题变成：长度为 $m$ 、每项在 $1\dots v$ 、和为 $k$ 的序列有多少个。

若 $k<m$ 或 $k>mv$ ，这样的序列不存在。否则令 $b_i=a_i-1$ ，问题变成

\sum b_i=k-m,\qquad 0\le b_i<v

先忽略上界，非负整数解有 $\binom{k-1}{m-1}$ 个。再用容斥扣掉至少有一个 $b_i\ge v$ 的情况。选定 $j$ 个越界变量，每个先减去 $v$ ，得到

\mathrm{cnt}=\sum_{j=0}^{\min(m,\lfloor(k-m)/v\rfloor)} (-1)^j\binom mj\binom{k-jv-1}{m-1}

答案就是 $v^n-\mathrm{cnt}$ ，最后取模。

也可以从生成函数看这一步：要求的是 $(x+x^2+\cdots+x^v)^m$ 中 $x^k$ 的系数。把它写成 $x^m(1-x^v)^m/(1-x)^m$ ，展开后就是同一个容斥式。

如果 $n<m$ ，数组里没有长度为 $m$ 的窗口，答案就是 0。

参考代码：直接计算容斥式

下面保留直接计算组合数的写法，用来对照公式。组合数上标可能接近 $10^9$ ，不能把阶乘一直预处理到上标；代码只对 $m$ 预处理，另一个组合数用乘积计算。这里的上标、下标都小于模数，可以这样求逆元。

这份代码最坏有 $O(m)$ 个容斥项，每项要花 $O(m)$ 计算组合数，总时间是 $O(m^2)$ ，空间是 $O(m)$ 。 $m=2\times10^5$ 时仍然会超时，这里先保留直接计算版。

MOD = 10**9 + 7


def comb_small_r(n, r):
    """C(n, r)，n 可以很大，r 不超过 2e5"""
    if r < 0 or n < r:
        return 0
    num = 1
    for i in range(r):
        num = num * ((n - i) % MOD) % MOD
    den = 1
    for i in range(1, r + 1):
        den = den * i % MOD
    return num * pow(den, MOD - 2, MOD) % MOD


def count_len_m(m, v, k):
    """长度为 m、每项 1..v、和为 k 的方案数"""
    if k < m or k > m * v:
        return 0

    # C(m, j) 用阶乘预处理
    fact = [1] * (m + 1)
    for i in range(1, m + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (m + 1)
    inv_fact[m] = pow(fact[m], MOD - 2, MOD)
    for i in range(m, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD

    total = 0
    S = k - m
    for j in range(S // v + 1):
        L = k - j * v - 1
        if L < m - 1:
            break
        term = fact[m] * inv_fact[j] % MOD * inv_fact[m - j] % MOD
        term = term * comb_small_r(L, m - 1) % MOD
        total += term if j % 2 == 0 else -term

    return total % MOD


def solve(n, v, m, k):
    total = pow(v, n, MOD)
    if n < m:
        return 0                          # 没有窗口，不存在和不等于 k 的窗口
    return (total - count_len_m(m, v, k)) % MOD

2026-04-11 某外卖厂暑期笔试复盘

2026-04-11 某外卖厂暑期笔试复盘

第一题：恰好选 x 组，使和为奇数

题目大意

思路分析

参考代码

第二题：连续窗口和与 m 周期数组计数

题目大意

思路分析

参考代码：直接计算容斥式

投稿をランダムに表示