CF Round988 div3

C

很简单的构造。
\(n \leq 4\)的时候是不可能的，很容易试探出来。
对于剩下的情况，由于偶数除了2都是合数，而两个不同的大于1的数的和均大于2，所以我们可以把奇数放一起，偶数放一起，此时只有分界处两数奇偶性不同，可能为质数。而此时我们可以选取4，5作为分界点的数。于是很容易构造出符合题意的排列。
code:

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
void solve()
{
    int n;
    cin >> n;
    if (n <= 4) {
        cout << -1 << endl;
    }
    else {
        vector<int>ans(n);
        ans[(n-1) / 2] = 5;
        ans[(n-1) / 2 + 1] = 4;
        int p = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1 && i != 5) {
                ans[p] = i;
                p++;
            }
        }
        p = (n -1)/ 2 + 2;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0 && i != 4) {
                ans[p] = i;
                p++;
            }
        }
        for (int i = 0; i < n; i++) {
            cout << ans[i] << " ";
        }
        cout << endl;
        
    }
    return;
}

D

也很简单。遍历整个障碍序列，对于每个障碍，贪心地选取可以选的最大的能量符直至可以跳过该障碍为止，然后再去考虑下一个障碍。
可以用一个优先队列来维护可供选择的能量符。
code:

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
void solve()
{
    int n, m, l;
    cin >> n >> m >> l;
    vector<pair<int, int>>a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    vector<pair<int, int>>b(m);
    for (int i = 0; i < m; i++) {
        cin >> b[i].first >> b[i].second;
    }
    priority_queue<int>q;
    int ans = 0;
    ll sum = 0;
    int pb = 0;
    for (int i = 0; i < n; i++) {
        while (pb < m && b[pb].first < a[i].first) {
            q.push(b[pb].second);
            pb++;
        }
        int len = a[i].second - a[i].first + 1;
        while (!q.empty() && sum < len) {
            ans++;
            sum += q.top();
            q.pop();
        }
        if (sum < len) {
            cout << -1 << endl;
            return;
        }
    }
    cout << ans << endl;
    return;
}

E

分析题意，我们需要选取一个合适的询问序列来确定这个01串。
考虑顺序询问区间 \([1,j],j = 2,3,...n\)，我们可以发现如果\(f(1,j)\)大于前面一个询问值，那么\(s[j]\)一定是\(1\),否则如果\(f(1,j) \neq 0\),则 \(s[j]\) 为0。
还剩余\(f[1,j] = 0\)的情况，我们考虑\(f\)第一次非0的位置，此时\(s[1,j]\)应该是形如\(11...10000...01\)的串，而0的个数为\(f\)，我们也很好确定前导 \(1\) 的个数。
最后，如果我们所有的询问得到的\(f\)全都为0，那么这个串是形如\(111...11000...00\)的串，而且无法确定0，1的个数，其他任何询问得到的\(f\)也均为0，所以按照题意我们应该输出IMPOSSIBLE.
code：

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
void solve()
{
    int n;
    cin >> n;
    string ans(n + 1, '0');
    int sum = 0;
    int flg = 1;
    for (int i = 2; i <= n; i++) {
        cout << "? " << 1 << " " << i << endl;
        cout.flush();
        int f;
        cin >> f;
        if (f > sum && flg) {
            sum = f;
            flg = 0;
            for (int j = 1; j <= i - f - 1; j++) {
                ans[j] = '1';
            }
            ans[i] = '1';
        }
        else if(f > sum && !flg){
            sum = f;
            ans[i] = '1';
        }
        else if (f == sum && flg) {
            ans[i] = '0';
        }
    }
    if (flg) {
        cout << "! IMPOSSIBLE" << endl;
    }
    else {
        ans[0] = ' ';
        cout << "!" << ans << endl;
    }
    return;

}

F

赛时没想到二分答案，还是太菜了。
实际上对于最少次数二分一下，check一下能不能即可。
check可以使用一个类似滑动窗口的算法，在给定攻击次数的情况下，计算出每个敌人可以被打死的左端点和右端点，然后把左端点数组和右端点数组排序，使用双指针计算同时在可击杀范围内最多敌人数即可。
时间复杂度\(O(n\log n \log H)\)
code:

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
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int>h(n), x(n);
    int maxh = 0;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        maxh = max(maxh, h[i]);
    }
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    int inf = INT_MAX / 2;
    int L = 1, R = maxh + 2;
    while (L < R) {
        int mid = (R + L) / 2;
        vector<int>l(n), r(n);
        for (int i = 0; i < n; i++) {
            int at = (h[i] + mid - 1) / mid;
            l[i] = x[i] - m + at;
            r[i] = max(l[i],x[i] + m - at + 1);
        }
        //stable_sort(l.begin(), l.end());
        //stable_sort(r.begin(), r.end());
        sort(l.begin(), l.end());
        sort(r.begin(), r.end());
        int p = -inf;
        int pl = 0, pr = 0;
        int cnt = 0;
        int ok = false;
        while (pl < n && pr < n) {
            if (l[pl] < r[pr]) {
                cnt++;
                pl++;
                if (cnt >= k) {
                    ok = true;
                    break;
                }
            }
            else if (l[pl] > r[pr]) {
                cnt--;
                pr++;
            }
            else {
                pl++;
                pr++;
            }
        }
        if (ok) {
            R = mid;
        }
        else {
            L = mid + 1;
        }
    }
    if (L == maxh + 2) {
        cout << -1 << endl;
    }
    else {
        cout << L << endl;
    }
    return;
}

G

很有意思和启发性的题，也算是在学习一些数论知识后第一次用到了莫比乌斯(Möbius)函数。 题意大概是一个有向图有编号为1-n的点，有点权\(v_i\)。当且仅当\(i < j\) 且 \(\gcd(a_i,a_j) \neq 1\)时有\(a_i\)到\(a_j\)的边。求点1到点n的路径数。点数为\(2 \sim 1e5\),点权范围为\(2 \sim 1e6\)。
首先，肯定不能两层循环预处理出所有路径，这是\(n^2\)的。但是考虑到路径与\(\gcd\)的关联，我们可以通过筛一个点权的所有因数，来获得图中的一个个团(虽然不是双向边)。而可以想到的是，质数对应的团是极大的。
考虑到这是一个有向图，我们如果把所有具有共同因数的点的集合先处理好了再计数，转移反而很麻烦。所以我们考虑边把点加进来边计数。
我们约定记号\(path[i]\)表示到下标为\(i\)的点的路径数，\(sum[fac]\)表示具有共同因子\(fac\)的所有点的路径数之和。
于是对于一个新加进来的点，到它的路径数应该等于和他具有相同非1因子的点的路径数的总和。显然我们不能一个一个去找这些点，否则算法复杂度最坏会到\(n^2\)，但是我们可以利用\(sum\)数组来求解。
如何用\(sum\)的组合来表示这个集合(指前面所述的具有相同非1因子的点)的贡献呢？我们从集合的角度考虑。假设新加进来的点权\(v = p_1^{k_1} p_2^{k_2}...p_k^{k_k}\),那么对于的集合应该是\(p_1,p_2,\dots,p_k\)这些质因数代表集合的并集。于是可以自然的想到容斥定理。按照容斥定理，我们考虑\(v\)的所有非1因子\(f\),并将其分成两类：
1. \(f\) 是 \(k\)个不同质数的乘积(可以是一个)，那么这代表着容斥公式中的一项。对节点的贡献是\((-1)^{k+1} \cdot sum[f]\)。
2. 存在质数\(p\),\(p^2 | f\)，那么这不是容斥公式中的一项(理解这点可以想象一下veen图，交集处每个质因子的幂次要么是1，要么是0)。那么它对节点的贡献是0,或者说，\(sum[f]\)前乘上的系数是0.

如果你学过Möbius函数，我们会发现我们在\(sum[f]\)前乘上的系数简直就是\(\mu(x)\)的定义！唯一不同的是正负刚好相反。

\(\mu\) 为莫比乌斯函数，定义为 \[\begin{align*} \mu(n)=\left\{ \begin{array}{ll} 1&n=1\\ 0&\exists p,p^2 | n\\ (-1)^k&n = p_1 \cdot p_2...p_k\\ \end{array} \right. \end{align*}\]

\(\mu\)是一个积性函数，而几乎所有的积性函数都可以使用欧拉筛法以线性时间筛出来，\(\mu\)并不例外。
于是我们可以预处理\(1 \sim 1e6\)范围内的\(\mu(x)\),然后对于每个新加进来的点，在\(\sqrt v\)内筛出所有因数，对于每个因数\(f\)，我们计入贡献\(-\mu(f) \cdot sum[f]\)。计算完后，再将这个节点的贡献加入所有它因数的集合贡献中去。
有计算公式：
\[ path[i] = \sum_{f|v_i} -\mu(f) \cdot sum[f] \] 于是我们得出一个这题的一个解法，时间复杂度\(O(n\sqrt V)\)。
(实际上对于和\(\gcd\)相关的容斥与莫比乌斯函数的深入联系仍值得探究，这里只是浅显地揭示了它们在形式上的对应关系，不过就容我先偷个懒吧，这件事以后再说)
code:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#define MAX_N 1000001
vector<int> prime;
vector<int> isprime(MAX_N, true);//bool  
vector<int> mu(MAX_N);

void get_mu(void)
{
    const int n = MAX_N - 1;
    mu[1] = 1;
    for (int i = 2; i < n; i++) {
        if (isprime[i]) {
            prime.push_back(i);
            mu[i] = -1;
            //index[i] = prime.size();
        }

        for (int j = 0; i * prime[j] < n; j++) {
            isprime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            else {
                mu[i * prime[j]] = -mu[i];
            }

        }

    }

}

template<class T>
constexpr T power(T a, i64 b) {
    T res{ 1 };
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x{ 0 } {}
    constexpr MInt(i64 x) : x{ norm(x % getMod()) } {}

    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        }
        else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        return power(*this, getMod() - 2);
    }
    constexpr MInt& operator*=(MInt rhs)& {
        if (getMod() < (1ULL << 31)) {
            x = x * rhs.x % int(getMod());
        }
        else {
            x = mul(x, rhs.x, getMod());
        }
        return *this;
    }
    constexpr MInt& operator+=(MInt rhs)& {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt& operator-=(MInt rhs)& {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt& operator/=(MInt rhs)& {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream& operator>>(std::istream& is, MInt& a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const MInt& a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
    friend constexpr bool operator<(MInt lhs, MInt rhs) {
        return lhs.val() < rhs.val();
    }
};

template<>
i64 MInt<0>::Mod = 998244353;


using Z = MInt<0>;

void solve()
{
    get_mu();
    int n;
    cin >> n;
    const int N = 1000001;
    vector<Z>path(N);
    vector<Z>node(n + 1);
    node[1] = 1;
    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        vector<int>fac;
        for (int j = 1; j <= sqrt(v); j++) {// use Möbius
            if (v % j == 0 ) {
                if (j != 1) {
                    node[i] += -mu[j] * path[j];
                    fac.push_back(j);
                }
                if (j * j != v) {                                                        
                    node[i] += -mu[v / j] * path[v / j];
                    fac.push_back(v / j);
                }
            }
        }

        for (auto p : fac) {
            path[p] += node[i];
        }
        
    }

    cout << node[n] << endl;
    return;

}

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

   
        solve();
    return 0;
}