「QFOI R1」摸摸

GitHub跳转原题关系图返回列表

折叠一次后 t 变成关于中心对称的向量，之后每折叠一次只翻倍；于是 b 只能是 x·t + H·(t+reverse(t)) 的形式，解出唯一的非负整数 x,H 再验证即可。

OJ: luogu

题目 ID: P9714

难度:普及

标签:数学推导思维枚举线性组合

创建: 2026-10-03 12:04

更新: 2026-10-03 12:04

形式化题目

给定长度为 $n$ 的数列 $t$ 和目标数列 $b$ ，另有 $a$ 初始全为 $0$ 。允许两种操作（可任意次、任意顺序）：

操作一： $t_i \leftarrow t_i + t_{n+1-i}$ ，对每个 $i$ 同时进行；
操作二： $a_i \leftarrow a_i + t_i$ 。

判断是否存在操作序列使 $a = b$ 。多组询问，只回答 Yes 或 No。

注意约束 $1 \leqslant \sum n \leqslant 2\times 10^3$ 、 $1 \leqslant t_i, b_i \leqslant 2\times 10^3$ ： $\sum n$ 很小，但值域也不大，所以甚至可以接受 $O(n \log b)$ 之类的做法；真正需要的是把"操作序列"这种看似无穷的可能空间压缩成有限个方程。

正解

思路

直接去想"先做几次操作一、再做几次操作二"是行不通的：操作可以任意交错，序列有无穷多条。我们的目标是把这无穷多条序列，压成有限个整数解。

第一步：两种操作互不干扰。

操作一只改写 $t$ ，完全不动 $a$ ；
操作二只改写 $a$ ，完全不动 $t$ 。

所以操作序列里，只有"在 $t$ 长成什么样的时候加了几次"才是重要的。设 $t$ 的初值为 $u$ ，记 $T^0 = u$ ，第 $k$ 次折叠之后的值是 $T^k$ 。再设 $x_k$ 表示"在 $t$ 的值恰好是 $T^k$ 时，执行了多少次操作二"，那么

b_i = x_0 u_i + x_1 T^1_i + x_2 T^2_i + \cdots + x_m T^m_i

一遍操作序列唯一对应一组非负整数 $x_0, x_1, \dots, x_m$ ，反过来给定这组数也一定构造得出，所以这是在两种描述之间建立了双射。序列的无穷性被这组 $(x_k)$ 吸收掉了。

第二步：算出每个 $T^k$ 到底长什么样。

令 $m(i) = n+1-i$ ，并记

v_i = u_i + u_{m(i)}

也就是 $u$ 与自己的倒序逐项相加， $v = T^1$ 。关键观察是：

一次折叠之后， $t$ 就变成关于中心对称的向量了。

因为 $v_{m(i)} = u_{m(i)} + u_{m(m(i))} = u_{m(i)} + u_i = v_i$ ，所以 $v$ 一定满足 $v_i = v_{m(i)}$ 。

那么对 $k \geqslant 1$ ，再折叠一次时：

T^2_i = T^1_i + T^1_{m(i)} = v_i + v_{m(i)} = 2v_i

同理 $T^3_i = T^2_i + T^2_{m(i)} = 2v_i + 2v_{m(i)} = 4v_i$ ，依此类推。由于对称性一旦成立就永远保持（ $v$ 对称 $\Rightarrow$ $2v$ 对称 $\Rightarrow$ $4v$ 对称 $\Rightarrow \cdots$ ），于是

T^k_i = 2^{k-1} v_i \qquad (k \geqslant 1)

看似要无限枚举的折叠过程，其实只有第一步是"新"的，后面全是 $v$ 的倍数。

第三步：合并成一个方程。

把上式代回 $b$ ：

b_i = x_0 u_i + \sum_{k\geqslant 1} x_k \cdot 2^{k-1} v_i = x_0 u_i + H\, v_i, \qquad H = \sum_{k \geqslant 1} x_k\, 2^{k-1}

现在看 $H$ 能取哪些值。因为 $x_k$ 可以取任意非负整数，把 $H$ 写成二进制、令 $x_k$ 取第 $k-1$ 个二进制位（ $x_1$ 是 $2^0$ 位、 $x_2$ 是 $2^1$ 位、……），就能凑出任意非负整数。

所以 $H$ 恰好可以取遍全体非负整数，不多也不少。

于是整个问题等价于一个非常干净的说法：

是否存在非负整数 $x_0, H$ ，使得对一切 $i$ 都有 $b_i = x_0 u_i + H v_i$ ？

只剩下两个未知量，解方程就够了。

第四步：解出 $x_0$ 和 $H$ 。

两个未知量需要两条方程。把 $i$ 与它的镜像 $m(i)$ 两条等式相减：

b_i - b_{m(i)} = x_0\bigl(u_i - u_{m(i)}\bigr) + H\underbrace{\bigl(v_i - v_{m(i)}\bigr)}_{=\,0} = x_0\bigl(u_i - u_{m(i)}\bigr)

因为 $v$ 对称， $H$ 被自动消掉了！这正是一次折叠带来的好处。于是分两种情况。

情形 A：存在 $i$ 使 $u_i \neq u_{m(i)}$ 。 取这样一个 $i$ （若 $n$ 为奇数，中间那个位置恒有 $u_i=u_{m(i)}$ ，所以只能从两侧找）。分母非零， $x_0$ 被唯一确定：

x_0 = \frac{b_i - b_{m(i)}}{u_i - u_{m(i)}}

要求它是非负整数（ $b_i - b_{m(i)}$ 必须能被整除，且商 $\geqslant 0$ ）。再把 $i=1$ 代回原式解出 $H$ ：

H = \frac{b_1 - x_0 u_1}{v_1}

同样要求非负整数。两个未知量都被钉死后， $O(n)$ 把所有位置验一遍即可。

情形 B： $u$ 本身完全对称，即所有 $u_i = u_{m(i)}$ 。此时 $v_i = 2u_i$ ，方程退化为

b_i = u_i(x_0 + 2H)

记 $K = x_0 + 2H$ 。由于 $x_0$ 可以是任意非负整数， $K$ 就能取遍全体非负整数（取 $x_0 = K, H = 0$ ）。所以只要所有 $b_i / u_i$ 都等于同一个整数 $K$ 就可行。

为什么这样是对的？ 上面每一步都是等价的（“存在操作序列” $\iff$ “存在非负整数 $x_0,H$ 满足方程”），而情形 A 中线性方程组的系数矩阵非奇异，解唯一，所以反解出来的值若通不过验证就一定无解；情形 B 也同理。两处都先解、后逐项验证，不需要相信"解出来了就完事"。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 12:04
 * update_at: 2026-10-03 12:04
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2005;

int n;
ll t[maxn]; // 题目给出的 t 数列
ll b[maxn]; // 目标数列

// 记 mirror(i) = n + 1 - i。
// 设第 k 个版本的 t 为 T^k（T^0 = t，每做一次操作一变成 fold(T^k)），
// 并且 x_k 表示用 T^k 做了几次操作二，则
//     a_i = x_0 * t_i + H * (t_i + t_mirror(i)),  H = sum_{k>=1} x_k * 2^(k-1) >= 0
// 其中 x_0 >= 0 与 H 都是可以任意取的非负整数。
// 于是答案就是：是否存在非负整数 x_0, H 使所有等式同时成立。
bool check() {
    // 情形 1：存在 i 使 t_i != t_mirror(i)。
    // 用 i 与 mirror(i) 两条等式相减，可以直接反解出 x_0。
    int pos = -1;
    for (int i = 1; i <= n; i++) {
        if (t[i] != t[n + 1 - i]) {
            pos = i;
            break;
        }
    }

    if (pos != -1) {
        int j = n + 1 - pos;
        ll num = b[pos] - b[j];    // = x_0 * (t_pos - t_j)
        ll den = t[pos] - t[j];    // 由 t_pos != t_j 保证 den != 0
        if (num % den != 0) return false;
        ll x0 = num / den;
        if (x0 < 0) return false;

        // 用 i = 1 的等式反解 H
        ll rest = b[1] - x0 * t[1];
        ll coef = t[1] + t[n];
        if (rest % coef != 0) return false;
        ll H = rest / coef;
        if (H < 0) return false;

        // 逐条验证
        for (int i = 1; i <= n; i++) {
            if (b[i] != x0 * t[i] + (t[i] + t[n + 1 - i]) * H) return false;
        }
        return true;
    }

    // 情形 2：t 完全对称，即所有 t_i == t_mirror(i)。
    // 此时等式退化为 b_i = t_i * (x_0 + 2H)，只要所有 b_i / t_i 是同一个整数即可
    // （取 x_0 等于这个整数、H = 0 就能实现）。
    if (b[1] % t[1] != 0) return false;
    ll K = b[1] / t[1];
    for (int i = 1; i <= n; i++) {
        if (b[i] != K * t[i]) return false;
    }
    return true;
}

void read_data() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> t[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        if (check()) cout << "Yes\n";
        else cout << "No\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    read_data();

    return 0;
}

实现上有两个容易写错的地方：

反解 $H$ 时用的是 $i=1$ 。这没问题，但必须在解完之后把所有 $i$ 重新验证一遍——因为解方程只用了两条等式，其余位置还没有被约束过。
情形 A 的除数为 $u_i - u_{m(i)}$ ， $i$ 必须是那两个不对称点之一，不能拿中间元素当除点（ $n$ 为奇数时中间的自减恒为 $0$ ，会除零）。

复杂度

每组数据只需 $O(n)$ 找不对称点、 $O(1)$ 反解、 $O(n)$ 验证。总时间复杂度 $O(\sum n)$ ，空间复杂度 $O(n)$ 。数值上 $x_0 \leqslant 2000$ 、 $u_i \leqslant 2000$ ，乘积不超过 $4 \times 10^6$ ，int 也不会溢出（代码中仍使用 long long 以防万一）。

关于暴力解法

对拍用的 brute.cpp 是直接搜索操作序列：状态为当前的 $(a,t)$ ，每层尝试操作一或操作二。

它依赖一个剪枝： $a$ 只增不减，而折叠后 $T^{k+1}_i = T^k_i + T^k_{m(i)} \geqslant T^k_i$ 也说明 $t$ 只增不减。所以只要某一刻出现 $a_i + t_i > b_i$ ，此后再也无法把 $b_i$ 补回来，可以立刻回溯。搜索树因此是有限的，可在小数据上稳定完成对拍。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 12:04
 * update_at: 2026-10-03 12:04
 */
// brute.cpp：小数据暴力解（仅用于理解题意与对拍，不做任何优化）。
// 直接搜索操作序列：状态就是当前的 (a, t) 两个数列，每一步尝试操作一或操作二。
//
// 剪枝依据：a 只会变大，t 在操作一之后也只会变大（新 t_i = t_i + t_{n+1-i} >= t_i），
// 所以只要某一刻出现 a_i + t_i > b_i，以后永远补不回来，可以立刻停止这条分支。
// 因此搜索树是有限的。本文件只在 t_i、b_i 都很小的数据上使用。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int n;
int a[maxn]; // 当前的 a
int t[maxn]; // 当前的 t
int b[maxn]; // 目标的 b

bool dfs() {
    // 已经达到目标
    bool same = true;
    for (int i = 1; i <= n; i++) {
        if (a[i] != b[i]) same = false;
    }
    if (same) return true;

    // 如果现在这个 t 都已经加不动，以后的 t 只会更大，更不可能加
    for (int i = 1; i <= n; i++) {
        if (a[i] + t[i] > b[i]) return false;
    }

    // 选择一：执行操作二，a += t
    for (int i = 1; i <= n; i++) a[i] += t[i];
    if (dfs()) return true;
    for (int i = 1; i <= n; i++) a[i] -= t[i];

    // 选择二：执行操作一，t 与自己的倒序相加。
    // 用本层的局部数组保存 t，避免不同递归层互相覆盖。
    int save_t[maxn];
    for (int i = 1; i <= n; i++) save_t[i] = t[i];
    for (int i = 1; i <= n; i++) t[i] = save_t[i] + save_t[n + 1 - i];
    if (dfs()) return true;
    for (int i = 1; i <= n; i++) t[i] = save_t[i];

    return false;
}

void read_data() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> t[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        for (int i = 1; i <= n; i++) a[i] = 0;
        if (dfs()) cout << "Yes\n";
        else cout << "No\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    read_data();

    return 0;
}

总结

这道题的关键不是"怎么搜索操作序列"，而是先消除操作序列的无限性：

两种操作互不干扰，于是任意操作序列等价于每个折叠版本各执行若干次操作二的计数；
折叠一次后 $t$ 就变成中心对称向量，此后每折叠一次只是整体乘 $2$ ，即 $T^k = 2^{k-1}v$ ；
二进制表示让"各计数的加权和" $H$ 恰好取遍所有非负整数，问题坍缩为 $b = x_0 u + H v$ 这一个方程；
利用 $v$ 的对称性作差消去 $H$ ，反解出唯一的 $x_0$ 和 $H$ ，非负整数 + 逐项验证即可。

值得记住的两个技巧：把"操作序列"转换成"各状态的执行次数"，以及用二进制把一个任意大的加权和解释成可以取遍所有非负整数。两者合起来就把无穷搜索变成了两条除法。

P9714 「QFOI R1」摸摸

题目描述

小 R 是一个可爱的女孩子，她喜欢被摸头。

但是摸头之前，必须答对她提出的一个问题。

她有一个长度为 $n$ 的数列 $a$ ，初始时所有元素均为 $0$ 。另有两个长度为 $n$ 的数列 $t,b$ 。

她可以进行两种操作：

将 $t$ 与 $t$ 的倒序对应元素相加，得到新的 $t$ 。
- 例如， $t=[1,4,2]$ 变为 $t'=[1+2,4+4,2+1]=[3,8,3]$ 。
将 $a$ 与 $t$ 对应元素相加，得到新的 $a$ 。
- 例如， $a=[1,2,3],t=[1,4,2]$ 变为 $a'=[1+1,2+4,3+2]=[2,6,5]$ 。

是否可能通过若干次以上操作将 $a$ 变为 $b$ ？

你希望摸她的头 $T$ 次，因此有 $T$ 组数据。

输入格式

第一行一个整数 $T$ ，表示数据组数。

对于每组数据：

第一行一个整数 $n$ ，表示数列长度。
第二行 $n$ 个整数，第 $i$ 个整数为 $t_i$ 。
第三行 $n$ 个整数，第 $i$ 个整数为 $b_i$ 。

输出格式

共 $T$ 行，每行一个为 Yes 或 No 的字符串，表示每组数据是否可能将 $a$ 变为 $b$ 。

字符串不区分大小写，如果答案为 Yes 的话，yes、YES、yEs 等都将被判为正确。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2Yes
No

说明/提示

样例解释

对于第一组数据：

初始时： $a=[0,0,0]$ ， $t=[1,2,2]$ ， $b=[5,8,7]$ 。
执行操作二： $a=[1,2,2]$ ， $t=[1,2,2]$ ， $b=[5,8,7]$ 。
执行操作二： $a=[2,4,4]$ ， $t=[1,2,2]$ ， $b=[5,8,7]$ 。
执行操作一： $a=[2,4,4]$ ， $t=[3,4,3]$ ， $b=[5,8,7]$ 。
执行操作二： $a=[5,8,7]$ ， $t=[3,4,3]$ ， $b=[5,8,7]$ 。

此时 $a=b$ ，符合要求。

对于第二组数据，可以证明不存在合法方案。

数据范围

本题共 $20$ 个测试点，每个测试点 $5$ 分。

记 $\sum n$ 表示每组数据的 $n$ 之和。

对于全部数据，保证 $1\le\sum n\le 2\times 10^3$ ， $n\ge 1$ ， $1\le t_i,b_i\le 2\times 10^3$ 。

对于测试点 $1\sim 4$ ：保证 $n\le 2$ 。
对于测试点 $5\sim 8$ ：保证所有 $t_i$ 都相等。
对于测试点 $9\sim 12$ ：保证 $b_i=b_{n-i+1}$ 。
对于测试点 $13\sim 16$ ：保证 $\sum n,t_i,b_i\le 200$ 。
对于测试点 $17\sim 20$ ：无特殊限制。

Hack 数据

本题在赛后添加了 Hack 数据，从 $21$ 开始编号。

原有测试点依然计 $5$ 分，Hack 数据计 $0$ 分，但只有通过所有数据才会被判为 Accepted。

为区分原有测试点和 Hack 数据，本题添加了子任务，但子任务的计分方式为“加和”，不会影响正常评测。

「QFOI R1」摸摸

目录

形式化题目

正解

思路

代码

复杂度

关于暴力解法

总结