安吉D5-T2 - Jerry's blog

原题呈现

题目描述#

给定一个长度为 $n$ 的环形序列 $a_1, a_2, \dots, a_n$ ．

其中每个位置的值满足：

若 $a_i = 0$ ，表示第 $i$ 个位置尚未确定；
若 $1 \le a_i \le n$ ，表示第 $i$ 个位置已经确定为编号 $a_i$ 的灵魂宝石．

你需要将所有值为 $0$ 的位置填上剩余未出现的数字，使得最终序列成为一个 $1$ 到 $n$ 的排列．

对于一个非负整数 $x$ ，定义 $\operatorname{cnt}(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数．

对于最终排列中一对相邻位置上的数字 $x, y$ ，如果 $\operatorname{cnt}(x \mathbin{\&} y)$ 与 $\operatorname{cnt}(x \mathbin{|} y)$ 的奇偶性不同，则称这对相邻数字达成了平衡．

其中 $\mathbin{\&}$ 表示按位与， $\mathbin{|}$ 表示按位或．

由于序列是环形的， $(a_n, a_1)$ 也相邻．

如果最终排列中的所有相邻数字对都达成了平衡，则称这个排列符合圆环之理．

现在有 $q$ 次观测修改．每次修改会将某个位置的值改为一个新的值，新的值可以是 $0$ ，也可以是 $1$ 到 $n$ 之间的整数．

请你分别求出初始状态以及每次修改之后，当前序列可以补全为符合圆环之理的排列数量．

两个补全方案不同，当且仅当至少存在一个位置，在两个最终排列中的数字不同．

答案对 $998244353$ 取模．

输入格式#

第一行包含两个整数 $n, q$ ，表示圆环长度和观测修改次数．

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示初始圆环状态．

接下来 $q$ 行，每行包含两个整数 $p, x$ ，表示一次观测修改：将 $a_p$ 修改为 $x$ ．

输出格式#

输出 $q+1$ 行．

第一行输出初始状态下的答案．

接下来第 $i$ 行输出第 $i$ 次修改后的答案．

样例#

输入 #1#

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

输出 #1#

数据范围#

本题采用捆绑评测，对于一个子任务，你必须通过其中的所有测试点才能得到对应分数．

子任务编号	分数	$n, q \le$	特殊性质
1	10	$10$	无
2	15	$18$	无
3	15	$2000$	无
4	15	$2 \times 10^5$	$q=0$
5	20	$2 \times 10^5$	保证任意时刻，序列中存在不为 $0$ 的位置
6	25	$2 \times 10^5$	无

对于全部数据：

$1 \le n \le 2 \times 10^5$ ；
$0 \le q \le 2 \times 10^5$ ；
$0 \le a_i \le n$ ；
$1 \le p \le n$ ；
$0 \le x \le n$ ．

观察题意中平衡的条件：若两个数， $\operatorname{cnt}(x \mathbin{\&} y) + \operatorname{cnt}(x \mathbin{|} y)$ 为奇数（根据题意，这里 $\operatorname{cnt}$ 等同于 $\operatorname{popcount}$ ），则这两个数平衡．又由于 $\operatorname{cnt}(x \mathbin{\&} y) + \operatorname{cnt}(x \mathbin{|} y) = \operatorname{cnt}(x) + \operatorname{cnt}(y)$ ，所以题意中平衡的条件转化为：

$\operatorname{popcount}$ 奇偶性不同的两个数相互平衡．

记 $\operatorname{popcount}$ 结果为奇数的正整数集合为 $s_1$ ，称其为一类数，结果为偶数的正整数集合是 $s_2$ ，称其为二类数，则合法序列必须满足：一类数（和 0）和二类数（和 0）交错排列，因此， $|s_1|$ 必须等于 $|s_2|$ ，否则就始终没有合法的方案．

定义 $c_{i,j}$ ， $i,j\in\{0,1\}$ ，表示在已知序列中， $\forall i \in [1,n]$ 满足是一类数（若 $i=1$ ）或是二类数（若 $i=0$ ）、且处于奇数（ $j=1$ ）或偶数（ $j=0$ ）位置的正整数的数量．

先遍历整个已知的序列，计算出 $c_{i,j}$ ，再判断以下条件是否成立：

没有重复的正整数
不存在 $i\in\{0,1\}$ ，满足 $c_{i,0}$ 和 $c_{i,1}$ 都不为 0．（保证不会有两个 $\operatorname{popcount}$ 奇偶性相同的数，一个在奇数位置上，一个在偶数位置上）

如果存在任意一个条件不成立，无解，输出 0．

否则，令 $cnt_0$ 表示已知序列二类数数量， $cnt_0=c_{0, 0} + c_{0, 1}$ ．令 $cnt_1$ 表示已知序列中一类数数量， $cnt_1=c_{1, 0} + c_{1, 1}$ ．

则存在 $f_1 = |s_1| - cnt_1$ 个可以自由分配位置的一类数，存在 $f_2 = |s_2| - cnt_2$ 个可以自由分配位置的二类数，最终结果为 $f_1!f_2!$ ．

特别的，若所有数字都是 0（ $cnt_1=cnt_2=0$ ），则一类数和二类数可以整体交换位置，答案要乘 2．

当需要修改时，只需要动态维护 $c$ 数组，再维护每一个数字出现几次（用于检查是否重复）即可．

标程

1
#include <bits/stdc++.h>
2
#define group(x) (__builtin_popcountll(x) % 2)
3
// 该内建函数（__builtin_popcount）可以计算一个数二进制表示中1的数量
4
using namespace std;
5
typedef long long ll;
6
const int N = 2e5 + 100;
7
const int MOD = 998244353;
8
int n, q, a[N], fac[N];
9
int c[2][2];
10
int cnt1 = 0, cnt0 = 0;
11
int rep = 0;
12
map<int, int> used;
13
// c[i][j] 表示当前序列中0/1类数在偶/奇位置上的一共有多少个．
14

15
int calFac(int x) {
16
    if (!fac[x]) {
17
        fac[x] = 1ll * calFac(x - 1) * x % MOD;
18
    }
19
    return fac[x];
20
}
21

22
void solve() {
23
    if (!((c[0][0] == 0 && c[1][1] == 0) || (c[0][1] == 0 && c[1][0] == 0))) {
24
        cout << 0 << endl;
25
        return;
26
    }
27
    int unused0 = cnt0 - (c[0][1] + c[0][0]);
28
    int unused1 = cnt1 - (c[1][1] + c[1][0]);
29
    ll ans = 1ll * calFac(unused0) * calFac(unused1) % MOD;
30
    if (c[0][1] + c[0][0] + c[1][1] + c[1][0] == 0) {
31
        (ans *= 2) %= MOD;
32
    }
33
    cout << ans << endl;
34
}
35

36
int main() {
37
#ifdef ONLINE_JUDGE
38
    freopen("circle.in", "r", stdin);
39
    freopen("circle.out", "w", stdout);
40
#endif
41
    cin >> n >> q;
42
    fac[0] = 1;
43
    for (int i = 1; i <= n; i++) {
44
        cin >> a[i];
45
        if (used[a[i]] != 0 && a[i] != 0) {
46
            rep++;
47
        }
48
        used[a[i]]++;
49
        if (a[i] != 0)
50
            c[group(a[i])][i % 2]++;
51
    }
52
    for (int i = 1; i <= n; i++) {
53
        if (group(i)) {
54
            cnt1++;
55
        } else {
56
            cnt0++;
57
        }
58
    }
59
    if (cnt1 != cnt0) {
60
        for (int i = 0; i <= q; i++) {
61
            cout << 0 << endl;
62
        }
63
        return 0;
64
    }
65
    if (!rep)
66
        solve();
67
    else
68
        cout << 0 << endl;
69
    for (int i = 1; i <= q; i++) {
70
        int p, x;
71
        cin >> p >> x;
72
        if (a[p]) {
73
            c[group(a[p])][p % 2]--;
74
            used[a[p]]--;
75
        }
76
        if (used[a[p]] == 1) {
77
            rep--;
78
        }
79
        a[p] = x;
80
        if (x) {
81
          c[group(x)][p % 2]++;
82
            used[x]++;
83
        }
84
        if (used[x] == 2) {
85
            rep++;
86
        }
87
        if (rep) {
88
            cout << 0 << endl;
89
            continue;
90
        }
91
        solve();
92
    }
93
}

音乐

音乐