Codeforces Round 1108 (Div. 2)

2026/7/17 1:07:22

在复健补题，由于多年退化水平比较低下，所以没有 E 和 F。

A. farmpiggie and Subset Sum

题意

考虑一个长度为偶数 \(n\) 的排列 \(p\)，这个排列会与它的下标相乘，得到一组数：

\[1 \cdot p_1, \; 2 \cdot p_2, \; 3 \cdot p_3, \; \dots, \; n \cdot p_n \]

对于这 \(n\) 个数，每一个数你都可以选择赋予它正号（\(+\)）、负号（\(-\)）或者不选（即乘以 \(0\)），然后对它们求和。

构造任意一个排列 \(p\) 并输出，使得不管怎么拼凑这几个数的符号，都无法让求和结果等于 1。

思路

考虑奇偶性，最容易想到的就是令每个 \(|i \cdot p_i|\) 都是偶数，即要么 \(i\) 为偶数，要么 \(p_i\) 为偶数，此时求和结果一定为偶数。

由这个思路，可以立即想到，从 \(\{1, 2, 3, 4, \dots, 2k-1, 2k\}\) 这样的标准排列开始构造，可以考虑：

偶数位置上的数和奇数位置上的数进行两两交换。特别地，为了写代码方便，可以让相邻数之间交换：\(\{2, 1, 4, 3, \dots, 2k, 2k-1\}\)
直接倒序输出：\(\{2k, 2k-1, \dots, 2, 1\}\)

即可通过本题。

B. ezraft and Array

题意

给定一个正整数 \(n\)，构造一个含 \(n\) 个不相同正整数的数组，使得数组之和能整除所有数组元素。

思路

考虑迭代构造。\(n = 1\) 略，\(n = 2\) 显然无解。

从 \(n = 3\) 开始考虑，显然有 \([1, 2, 3]\) 满足题意。

现在考虑从 \(n\) 递推到 \(n+1\)：对于满足题意的数组 \(a_n\)，一个很自然的想法是把 \(\sum(a_n)\) 塞入到原来的 \(a_n\) 数组里来构造新的数组 \(a_{n+1}\)，此时新数组的和为 \(2 \sum{a_n}\)，而：

\(\sum{a_n}\) 能够整除原数组里所有的正整数 \(a_1, \dots, a_n\)，这是原数组 \(a_n\) 满足的条件
\(2 \sum{a_n}\) 又显然能够整除 \(a_{n + 1} = \sum{a_n}\)

于是直接从 \(\{1, 2, 3\}\) 开始递推求解数组就可以了。

C. 0mar and Alternating Sums

题意

定义一个数组 \(b\) 的 交错和（alternating sum） 为：\(\sum_{i = 1}^k (-1)^{i+1} b_i\)。

给定一个长度为 \(n\) 的不下降数组 \(a\)，元素 \(a_i\) 满足：要么是 \(-1\)，要么是正整数。现在找出数组 \(a\) 中所有满足交错和为 \(0\) 的子序列，对结果取模 \(10^9 + 7\)。

思路

先考虑第一种情况：数组中没有 \(-1\)。

首先，显然子序列的长度必须为偶数，设其长度为 \(2k\)。任取子序列中的两项 \(c_{2m-1}, c_{2m}\)，对交错和的贡献为 \(c_{2m - 1} - c_{2m}\)；又因为原数组不下降且都为正，则 \(c_{2m - 1} - c_{2m} \le 0\)。要想子序列的交错和为 0，则进一步必须满足 \(\forall m, c_{2m-1} = c_{2m}\)。

有了这个结论之后，回到原数组筛选子序列。考虑 \(a\) 中所有元素相同的一个极大子数组 \(sa\)，假设其长度为 \(k\)，必须在其中选择偶数个值才能保证交错和为 0，否则 \(c_{2m - 1} \ne c_{2m}\)。方案数量为：

\[C_{k}^0 + C_{k}^2 + C_{k}^4 + \dots = 2^{k-1} \]

考虑乘法原理，统计所有元素相同的极大子数组的大小 \(k_1, k_2, k_3, \dots\) 的数量，此时 \(\prod_i 2^{k_i-1}\) 即为答案。

现在考虑第二种情况：数组中有 \(-1\)。

如果在子序列中引入偶数个 \(-1\)，则这部分对交错和的贡献会相互抵消成 \(0\)，因此子序列中 \(-1\) 之后的部分对交错和的贡献仍然需要为 \(0\)，这退化到了第一种情况；否则，如果在子序列中引入奇数个 \(-1\)，此时需要后半部分的交错和为 \(1\) 才能抵消。

很容易想到这怎么实现：对于数组内元素相同的两个极大子数组 \(sa_1, sa_2\)，如果它们的元素值分别为 \(a_{sa_1}, a_{sa_2}\) 且 \(a_{sa_2} - a_{sa_1} = 1\)，那么可以从这两个子数组里各取奇数个值，其他子数组里取偶数个值，方案数仍然为 \(\prod_i 2^{k_i-1}\)。

综合这两种情况，答案计算如下：

当数组中不存在 \(-1\) 时，方案数为 \(\prod_i 2^{k_i-1}\)
当数组中存在 \(-1\) 时，方案数为 \(d \cdot \prod_i 2^{k_i-1}\)，d 为原数组元素大小相邻的对数

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef long double ld;
typedef std::vector<int> vi;#define forn(i, a, b) for(int i = a; i < b; i++)
#define readi(x) scanf("%d", &x)
#define readv(x, n) forn(i,0,n) scanf("%d", &x[i])#ifdef DEBUG
#define printi(x) printf("DEBUG: %d\n", x)
#define prints(x) printf("%s", x)
#define printv(x, n) printf("DEBUG: "); forn(i,0,n) printf("%d ", x[i])
#else
#define printi(x) printf("%d\n", x)
#define prints(x) cout << x << endl
#define printv(x, n) forn(i,0,n) printf("%d ", x[i])
#endifconst ll MOD = 1e9 + 7;
const int N  = 2e5 + 5;ll _pow[N];void pre(void) {_pow[0] = 1;forn (i, 1, N)_pow[i] = (_pow[i - 1] << 1) % MOD;
}int main(void){pre();int t;readi(t);while (t--) {int n;readi(n);ll ans = 0, _exp = 1;bool is_minus_one_exist = false;int last_num = -100, cnt = 0, adj_num = 0;while (n--){int tmp;readi(tmp);if (tmp == -1)is_minus_one_exist = true;if (tmp == last_num)cnt++;else {if (tmp - last_num == 1)adj_num++;_exp += cnt - 1;last_num = tmp;cnt = 1;}}_exp += cnt - 1;if (is_minus_one_exist)ans = (adj_num + 1) * _pow[_exp];elseans = _pow[_exp];printf("%llu\n", ans % MOD);}
}