A. Dinner Time 题解

题目分析

给定四个整数 $n, m, p, q$，我们需要判断是否存在一个整数数组 $a_1, a_2, \ldots, a_n$，满足：

1. 所有元素之和等于 $m$：$\sum_{i=1}^n a_i = m$
2. 每 $p$ 个连续元素之和等于 $q$：$\sum_{j=i}^{i+p-1} a_j = q$，对所有 $1 \leq i \leq n-p+1$

元素可以是负数，这给了我们很大的构造空间。

---

数学推导

1. 周期性

考虑相邻的两个条件：

对于 $i$ 和 $i+1$，有：

$$a_i + a_{i+1} + \cdots + a_{i+p-1} = q$$ $$a_{i+1} + a_{i+2} + \cdots + a_{i+p} = q$$

两式相减得：

$$(a_{i+1} + \cdots + a_{i+p-1} + a_{i+p}) - (a_i + a_{i+1} + \cdots + a_{i+p-1}) = 0 $$$$a_{i+p} - a_i = 0$$

因此：

$$a_{i+p} = a_i$$

这个等式对所有 $1 \leq i \leq n-p$ 成立。这意味着数组是周期为 $p$ 的周期序列：

$$a_1 = a_{1+p} = a_{1+2p} = \cdots$$ $$a_2 = a_{2+p} = a_{2+2p} = \cdots$$ $$\cdots$$ $$a_p = a_{2p} = a_{3p} = \cdots$$

---

2. 周期表示

设周期内的 $p$ 个元素为 $b_1, b_2, \ldots, b_p$，其中 $b_j = a_j$。那么整个数组可以表示为：

$$a_i = b_{(i-1) \bmod p + 1}$$

周期内元素满足：

$$b_1 + b_2 + \cdots + b_p = q$$

---

3. 总和计算

数组长度 $n$ 可以写成：

$$n = k \cdot p + r$$

其中 $k = \lfloor n/p \rfloor$ 是完整周期数，$r = n \bmod p$ 是剩余元素个数（$0 \leq r < p$）。

那么数组的总和为：

$$\sum_{i=1}^n a_i = k \cdot \sum_{j=1}^p b_j + \sum_{j=1}^r b_j = k \cdot q + S_r $$

其中 $S_r = \sum_{j=1}^r b_j$ 是周期中前 $r$ 个元素的和。

---

4. 可行性分析

我们需要判断是否存在整数 $b_1, \ldots, b_p$ 满足：

• $\sum_{j=1}^p b_j = q$
• $\sum_{j=1}^n a_i = k \cdot q + S_r = m$

即：

$$S_r = m - k \cdot q$$

现在问题转化为：是否存在长度为 $p$、和为 $q$ 的整数序列，其前 $r$ 项和为某个给定值 $x = m - k \cdot q$？

---

5. 分类讨论

情况 1：$r = 0$（即 $n$ 能被 $p$ 整除）

此时 $S_r = 0$，所以条件变为：

$$m = k \cdot q$$

因为 $k = n/p$，所以需要 $m = (n/p) \cdot q$。

结论：当 $n \% p = 0$ 时，有解当且仅当 $m = (n/p) \cdot q$。

情况 2：$r > 0$（即 $n$ 不能被 $p$ 整除）

此时 $1 \leq r < p$。我们需要证明：对任意整数 $x$，都可以构造出满足条件的序列。

构造方法如下：

• 令 $b_1 = x$，$b_2 = b_3 = \cdots = b_r = 0$
• 则前 $r$ 项和为 $x$
• 剩余 $p-r$ 项需要和为 $q - x$
• 令 $b_{r+1} = q - x$，$b_{r+2} = \cdots = b_p = 0$

由于 $p - r \geq 1$，这种构造总是可行的。因此，当 $r > 0$ 时，对任意 $m$ 都存在解。

---

最终结论

根据以上推导，判断条件如下：

• 如果 $n \% p = 0$，则需要 $m = (n/p) \cdot q$
• 如果 $n \% p \neq 0$，则总是有解（输出 "YES"）

---

算法实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m, p, q;
        cin >> n >> m >> p >> q;
        
        if (n % p == 0 && (n / p) * q != m) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
    
    return 0;
}

---

复杂度分析

• 时间复杂度：$O(t)$，每个测试用例 $O(1)$
• 空间复杂度：$O(1)$

---

示例验证

以题目给出的示例进行验证：

$n$	$m$	$p$	$q$	$n \% p$	条件判断	结果
3	2		1	1 ≠ 0	总是 YES	YES
1				0，$(1/1)\cdot1 = 1 = m$	YES
5	4	2	3	1 ≠ 0	总是 YES
10	7	5	2	0，$(10/5)\cdot2 = 4 \neq 7$	NO
4		1	3	0，$(4/1)\cdot3 = 12 \neq 4$

与题目输出完全一致 ✓

---

总结

本题的关键在于发现数组的周期性性质：由每 $p$ 个连续元素和相等可推出 $a_{i+p} = a_i$。利用这一性质，将问题转化为判断周期序列能否满足总和条件，最终得到简洁的判断公式。