Problem A. 新太阳睡觉中心

Input file: standard input

Output file: standard output

Time limit: 2 seconds

Memory limit: 512 megabytes

’Cause morning rolls around, and it’s another day of sun!

但是作为一个睡瘾患者，肖恩经常睡觉睡个半天，因此，当他醒来时，他甚至记不清今天是星期几。

所以从某一天开始，他开始进行记录：每次他醒来的时候，他就会写下一个数字，表示此时外面是否有阳光。如果有，他会写一个 1；否则，他会写一个 0。在完成记录后，还没等太阳下山，或是太阳升起，他又再次入睡。假设每次肖恩醒来时，他看到的要么是阳光，要么是月光，但不会同时看到两者。

这些记录下来的数字实际上形成了一个长度为 n 的数组：[a1*, a2, . . . , an] (∀1 ≤ i ≤ n, 0 ≤ ai ≤ 1)，其中ai* 表示肖恩写下的第 i 个数字。

然而，随着时间的推移，一些写下的数字变得模糊不清，你无法判断它是 1 还是 0。如果有 k 个数字无法识别，则可能有 $2^k$ 种不同的数组。

对于每个可能的数组，你都可以依据这个数组计算肖恩看到阳光的最小天数。如果将可能的不同数组的最小天数结果相加，得到的结果如何呢？由于答案可能很大，请将结果关于 998 244 353 取模后输出。

Input

每组测试包含多个测试用例。第一行是测试用例的数量 T (1 ≤ T ≤ $10^4$ )。

每个测试用例由两行组成。

第一行包含一个整数 n (2 ≤ n ≤ 5 × $10^5$ )，表示笔记的数量。

第二行包含 n 个整数 a1*, a2, . . . , an* (−1 ≤ ai ≤ 1)，表示每个记录下来的数字。只有当 ai = −1 时，数字是未知的。

可以保证单组测试中， $\sum$n 不会超过 5 × $$10^5$$。

Output

对于每个测试用例，输出 1 个整数 — 不同数组的最小天数求和后，对 998 244 353 取模的结果。

Example

standard input

1
2
3
4
5
6
7
3
3
1 0 1
3
0 0 0
3
1 -1 1

standard output

1
2
3
2
0
3

Note

在第一个测试用例中，当肖恩记录第一个和第三个数字 1 时，他看到的阳光一定是两个不同的天的。

在第二个测试用例中，肖恩从未看到阳光，因此答案是 0。

在第三个测试用例中，数组可能是 [1*,* 1*,* 1] 或 [1*,* 0*,* 1]。如果数组是 [1*,* 1*,* 1]，那么这些数字可能都是同一天被记录下来的，因此结果是 1。如果数组是 [1*,* 0*,* 1]，那么与第一个测试用例一致，结果为 2。将两种情况的答案求和，结果是 1 + 2 = 3。

题解：

“最小阳光天数” 的总和相当于：所有位置在所有可能数组中作为 “新阳光段起始点” 的次数之和。

而能作为起始点的位置i需满足：

  1. 该位置的值为 1（或 - 1 替换为 1）；
  2. 前一个位置i-1的值不为 1（或 - 1 替换为 0）（若i=0则无此限制）。

累加每个位置作为起始点的次数即为答案。

1. 预处理

由于 - 1 可替换为 0 或 1，总共有$2^k$种可能数组（k是 - 1 的数量）。预计算v[i] = $2^i$ mod 998244353，可以快速得到当前位置的贡献的大小。

2. 遍历每个位置计算贡献

对每个位置i，计算起始点次数：

1.i=0（第一个元素） 只需满足 i 位置为 1 ：

  • 若原数组a[0] = 1：所有k个 - 1 可任意替换，贡献为v[k]；
  • 若原数组a[0] = -1：需将其固定为 1，剩余k-1个 - 1 可任意替换，贡献为v[k-1]（若k≥1）；
  • 若原数组a[0] = 0：无法作为起始点，贡献为 0。

2.i>0（非第一个元素） 需满足 i 位置为 1 且 i-1不为 1 ：

  • 若前一个位置a[i-1] = 1：无法作为起始点，贡献为 0；
  • 否则，计算 “固定 - 1 的数量”：
    • 若a[i] = -1：需固定为 1（+1）；
    • 若a[i-1] = -1：需固定为 0（+1）；
  • 剩余可自由替换的 - 1 数量为k - 固定数，贡献为v[剩余数]（若剩余数≥0）。

代码

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
const int MAX=5e5+10;
vector<ll> v(MAX);
int main(){
    v[0]=1;
    for(int i=1;i<MAX;++i) v[i]=(v[i-1]*2)%MOD;
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        vector<ll> a(n);
        int k=0;
        for(int i=0;i<n;++i){
            cin>>a[i];
            if(a[i]==-1)k++;
        }
        
        ll ans=0;
        for(int i=0;i<n;++i){
            if(a[i]==0)continue;
            if(i==0){
                if(a[i]==1)ans=(ans+v[k])%MOD;
                else if(k>=1)ans=(ans+v[k-1])%MOD;
            }
            else{
                ll p=a[i-1];
                if(p==1)continue;
                ll c=0;
                if(a[i]==-1)c++;
                if(p==-1)c++;
                ll t=k-c;
                if(t>=0)ans=(ans+v[t])%MOD;
            }
        }
        cout<<ans%MOD<<endl;
    }
    return 0;
}

时间复杂度：O(Tn)

Problem B. 位完美

Input file: standard input

Output file: standard output

Time limit: 2 seconds

Memory limit: 512 megabytes

军蚁正在为一场残酷的战争做准备，但事情变得比他们想象的更复杂。

队伍中有 n 只军蚁。最初，每只军蚁 i (1 ≤ i ≤ n) 的力量为 ai。

然而，在战争期间会发生一些奇怪的事情：一股神秘力量会随机选择一个二元组 (i, j) (1 ≤ i < j ≤ n)，

而选择后，蚂蚁 i 和蚂蚁 j 会消失，并且一只新蚂蚁会替代它们神奇地出现，其力量为 ai ⊕ aj，即 ai和 aj 的按位异或（XOR）。

这种情况非常罕见，在整个战争中最多只会发生一次。

蚂蚁们认为整个队伍的总力量为$\sum_{i=1}^{n}$ $2^{a_i}$ ，如果那件”奇怪的事”永远不会减少军队的整体力量，则这个军队被认为是 位完美 的。

由于忙于练兵，蚂蚁们没有足够的时间来检查队伍是否位完美。你能帮帮他们吗？可能会有 T 支不同的军队。

Input

每组测试包含多个测试用例。第一行包含测试用例的数量 T (1 ≤ T ≤ 105 )。

每个测试用例由两行组成。

第一行包含一个整数 n (2 ≤ n ≤ 5 × 105 )，表示队伍中蚂蚁的数量。

第二行包含 n 个整数 a1*, a2, . . . , an* (1 ≤ ai ≤ 1018)，表示每只蚂蚁的力量。

保证在单组测试中， Pn 不会超过 5 × 105。

Output

对于每个测试用例，如果该军队是 位完美 的，则输出 YES，否则输出 NO。你可以以任意大小写打印答案。

Input

1
2
3
4
5
6
7
3
2
3 5
4
1 2 4 8
3
1 2 3

Output

1
2
3
YES
YES
NO

Note

在第一个测试用例中，如果两只蚂蚁合并，由于 3 ⊕ 5 = 6，整个队伍的总力量从 $2^3$ + $2^5$ = 40 变为

$2^6$ = 64，因此该事件不会减少总力量。所以该队伍是位运算完美。

题解

问题的核心在于：任意一对蚂蚁合并后阵容的总强度不会降低。

  1. 重复力量降低：使用 set 存储蚂蚁的力量值，检查是否存在重复的力量值。如果存在重复，那么合并后一定会降低阵容的总强度，故直接输出 “NO”。
  2. 枚举：对于每一对不同的蚂蚁 (i, j)，计算合并后的力量值 a[i] ^ a[j]。如果合并后总强度降低，则输出 “NO”。
  3. 结果：如果所有蚂蚁对合并后总强度都不降低，则输出 “YES”。

代码

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    int T;cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {cin >> a[i];}
        set<long long> s(a.begin(), a.end());
        if (s.size() != n) {
            cout<<"NO\n";
            continue;
        }
        bool f = true;
        for (int i = 0; i < n && f; i++) {
            for (int j = i + 1; j < n; j++) {
                ll x = min(a[i], a[j]);
                ll y = max(a[i], a[j]);
                ll d = y - x;
                ll b = x & y;
                ll tt = y - 2 * b;
                if (tt < 0 || (tt >= 0 && tt <= d)) {
                    f = false;
                    break;
                }
            }
        }

        if (f) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

时间复杂度

  • 时间复杂度： O($Tn^2$)