2022 年杭电多校第九场补题记录

A Arithmetic Subsequence

题意：给定一个长度为 $n$ 的序列，对它进行重新排序使得它不存在等差子序列。$n\le 5\times 10^3$。

解法：首先如果一个数字出现大于等于 $3$ 次，则一定无解。

考虑一个等差子序列的二进制构成：$x,y,z$。首先都丢弃掉共同的最低位的 $0$，考虑公差为 $1$ 的情况（公差更大的同理），则有 $x=(01\cdots 01)$，$y=(01\cdots 10)$，$z=x=(01\cdots 11)$，前面完全相同。则只有让 $y$ 排列在 $x,z$ 之前或者之后才行。注意到 $x,z$ 同奇偶而 $y$ 不同，因而可以按照末尾对其排序，则可以顺利让 $x,z$ 置于 $y$ 前或后。同理对公差更大的序列也可以进行类似的操作。因而最后的答案就是对数字按照 $\mathrm{bitrev}$ 的大小进行排序即可。总时间复杂度 $\mathcal{O}(n\log n)$。

#include 
using namespace std;
unsigned rev(unsigned x)
{
    unsigned ans = 0;
    for (int i = 31; i >= 0; i--, x >>= 1)
        ans |= (x & 1) << i;
    return ans;
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        map<int, int> times;
        vector<pair<unsigned, unsigned>> a(n);
        bool flag = 1;
        for (int i = 0; i < n;i++)
        {
            scanf("%u", &a[i].second);
            times[a[i].second]++;
            a[i].first = rev(a[i].second);
        }
        for(auto i:times)
            if(i.second >= 3)
            {
                flag = 0;
                break;
            }
        if(!flag)
        {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        sort(a.begin(), a.end());
        for (auto i : a)
            printf("%d ", i.second);
        printf("\n");
    }
    return 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
41
42
43
44

C Fast Bubble Sort

题意：给定长度为 $n$ 的排列 { p i } \{p_i\} {pi​}，$q$ 次询问 $[l,r]$，问该区间需要经过多少次子区间旋转平移操作（即，$a_i{a}_{i+1}\cdots a_j\to a_{i+1}\cdots a_j{a}_i$ 或 $a_i{a}_{i+1}\cdots a_j\to a_j{a}_i{a}_{i+1}\cdots a_{j-1}$），变成 $B(p[l,r])$。其中 $B(p[x,y])$ 操作如下：

int* B(int *p, int x, int y)
{
    for(int i=x;i<y;i++)
        if(p[i]>p[i+1])
            swap(p[i],p[i+1]);
    return p;
}
1
2
3
4
5
6
7

$n,q\le 1\times 10^5$。

解法：利用单调栈求出每个点后面第一个比它大的值在哪里，第 $i$ 个数字记为 $R_i$。若 $r_i=i+1$，则必然不会交换；否则它就会有交换操作，且直接交换到 $R_p$。对应于可执行操作，就是一次旋转平移。同时，若满足 $i<j\le r_j\le r_i$，则 $j$ 不会被交换。考虑倍增，$f_{i,j}$ 表示从第 $i$ 个点开始经历 $2^j$ 次旋转平移操作所到达的点。若抵达最后一个跳跃点 $p$，且 $R_p\ge r$，若 $R_p=p+1$ 则不经历旋转平移，否则还需要一次旋转平移。

#include
using namespace std;
const int N = 100000;
int a[N + 5], r[N + 5], nx[N + 5], f[N + 5][20];
int main()
{
    int t, n, q;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= n;i++)
        {
            r[i] = n + 1;
            for (int j = 0; j < 20;j++)
                f[i][j] = 0;
        }
        for (int j = 0; j < 20;j++)
            f[n + 1][j] = n + 1;
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        stack<int> s;
        for (int i = n; i >= 1;i--)
        {
            while (!s.empty() && a[s.top()] < a[i])
                s.pop();
            if(!s.empty())
                r[i] = s.top();
            else
                r[i] = n + 1;
            s.push(i);
        }
        f[n + 1][0] = nx[n + 1] = n + 1;
        for (int i = n; i >= 1;i--)
        {
            if(r[i] > i + 1)
            {
                nx[i] = i + 1;
                f[i][0] = r[i];
            }
            else
            {
                f[i][0] = f[r[i]][0];
                nx[i] = nx[i + 1];
            }
        }
        for (int i = 1; i < 20; i++)
            for (int j = 1; j <= n + 1; j++)
                f[j][i] = f[f[j][i - 1]][i - 1];
        while(q--)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            int ans = 0, place = l;
            for (int i = 19; i >= 0;i--)
                if (f[place][i] <= r)
                {
                    place = f[place][i];
                    ans += 1 << i;
                }
            printf("%d\n", ans + (nx[place] <= r));
        }
    }
    return 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
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

F Mario Party

题意：给定长度为 $n$ 的序列 { a n } \{a_n\} {an​}，$q$ 次询问，每次从 $l$ 号节点出发，初始钱数为 $x$，走到 $i+1$ 节点的时候若 $x+a_{i+1}\ge 0$ 则 $x\leftarrow x+a_{i+1}$，否则不变，问抵达 $r$ 节点时的钱数。$n,q\le 5\times 10^5$，$\sum |a_i|\le 1\times 10^6$。

解法：考虑在第 $i$ 个节点的时候，两次询问里面人的钱数相同，则他们两个可以认为是一个人。

首先离线，然后从左到右遍历序列的时候维护一个询问的并查集。对于 $a_i\ge 0$ 的情况，那么显然它不会合并询问；否则，对于钱数为 $x$ 和钱数为 $x-a_i$ 的询问，就需要合并成一个询问。

考虑加入询问：如果当前的钱数没人了，则新建一个点；否则合并入并查集中，同时利用并查集维护每个询问的起始钱数对应于现在的钱数。回答只需要在并查集中查询对应的钱数即可。总时间复杂度 $\mathcal{O}(n+q)$。

#include 
using namespace std;
const int N = 1000000;
int p[3 * N + 5], pos[3 * N + 5];
class DSU
{
    vector<int> father;

public:
    DSU(int n)
    {
        father.resize(n);
        for (int i = 0; i < n;i++)
            father[i] = i;
    }
    int getfather(int x)
    {
        return father[x] == x ? x : father[x] = getfather(father[x]);
    }
    void merge(int v, int u)
    {
        u = getfather(u), v = getfather(v);
        if (u != v)
            father[u] = v;
    }
};
int main()
{
    int caset, n, q;
    scanf("%d", &caset);
    for (int o = 1; o <= caset;o++)
    {
        scanf("%d%d", &n, &q);
        for (int i = 0; i <= 3 * N; i++)
        {
            p[i] = -1;
            pos[i] = 0;
        }
        DSU t(q);
        auto merge = [&](int u, int v)
        {
            assert(u <= 2 * N && u >= 0);
            assert(v <= 2 * N && v >= 0);
            if (p[u] == -1)
                return;
            if (p[v] == -1)
            {
                p[v] = p[u];
                pos[p[v]] = v;
            }
            else
                t.merge(p[v], p[u]);
            p[u] = -1;
        };
        int start = N;
        vector<int> a(n), ans(q), x(q);
        vector<vector<int>> add(n), del(n);
        for (int i = 0; i < n;i++)
            scanf("%d", &a[i]);
        for (int i = 0, l, r; i < q;i++)
        {
            scanf("%d%d%d", &l, &r, &x[i]);
            add[l - 1].push_back(i);
            del[r - 1].push_back(i);
        }
        for (int i = 0; i < n;i++)
        {

            if (a[i] < 0)
                for (int j = start; j < start - a[i];j++)
                    merge(j, j - a[i]);
            start -= a[i];
            for (auto j : add[i])
            {
                int now = x[j] + start;
                if(p[now] == -1)
                {
                    p[now] = j;
                    pos[j] = now;
                }
                else
                    t.merge(p[now], j);
            }
            for (auto j : del[i])
                ans[j] = pos[t.getfather(j)] - start;
        }
        for (auto i : ans)
            printf("%d\n", i);
    }
    return 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
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

G Matryoshka Doll

题意：给定 $n$ 个盒子的大小 { a i } \{a_i\} {ai​}，一个大小为 $x$ 的盒子能放入大小为 $y$ 的盒子中当且仅当 $x+r\le y$。问将这 $n$ 个盒子分成 $k$ 组，每一组中小盒子都能完全放入本组任何比它大的盒子中的方案数。$n,k\le 5\times 10^3$。

解法：首先按照大小对 $a_i$ 排序。考虑 $f_{i,j}$ 表示前 $i$ 小的盒子分成 $j$ 堆的方案数，则 $f_{i,j}\leftarrow f_{i-1,j-1}+f_{i-1,j}\max (0,j-c_i)$，其中 $c_i$ 表示前 $i$ 个盒子中有多少个盒子不能放入第 $i$ 个盒子。$f_{i-1,j}\max (0,j-c_i)$ 的含义为，第 $i$ 个盒子只能和前面所有的堆中，最大的盒子满足 $a_j+r\le a_i$ 放在一堆，对于不能被 $a_i$ 放进去的盒子，它一定会被单独的列在别的堆中。预处理 $c_i$ 后总时间复杂度 $\mathcal{O}(n^2)$。

#include 
using namespace std;
const int mod = 998244353;
const int N = 5000;
int f[N + 5][N + 5], a[N + 5], l[N + 5];
int main()
{
    int t, n, k, r;
    scanf("%d", &t);
    while(t--)
    {
        memset(f, 0, sizeof(f));
        scanf("%d%d%d", &n, &k, &r);
        for (int i = 1; i <= n;i++)
            scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        l[1] = 1;
        for (int i = 2; i <= n;i++)
        {
            int st = l[i - 1];
            while(st <= i && a[st] <= a[i] - r)
                st++;
            l[i] = st;
        }
        for (int i = 1; i <= n;i++)
            f[i][i] = 1;
        for (int i = 2; i <= n;i++)
            for (int j = 1; j < i && j <= k;j++)
                f[i][j] = (f[i - 1][j - 1] + 1ll * f[i - 1][j] * max(0, j - (i - l[i])) % mod) % mod;
        printf("%d\n", f[n][k]);
    }
    return 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

H Shortest Path in GCD Graph

题意：有 $n$ 个点的图，第 $i$ 个节点和第 $j$ 个节点之前有一条边权为 $\gcd (i,j)$ 的边。$q$ 次询问从 $x$ 到 $y$ 节点的最短路长度和最短路条数。$n\le 1\times 10^7$，$q\le 5\times 10^4$。

解法：若 $\gcd (x,y)=1$，则最短路长度为 $1$，条数也为 $1$。否则一定可以通过 $i\to 1\to j$ 以长度为 $2$ 抵达。考虑符合条件的最短路条数，必须满足 $\gcd (x,i)=1$ 且 $\gcd (y,i)=1$，即是计算 $\sum _{i=1}^n[\gcd (i,\mathrm{lcm}(x,y))=1]$。设 $u=\mathrm{lcm}(x,y)$，有：
$$\begin{array}{rl}\sum _{i=1}^n[\gcd (i,u)=1]=& \sum _{i=1}^n\sum _{d|u}\mu (d)\\ =& \sum _{d|u}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }1\\ =& \sum _{d|u}\mu (d)\lfloor \frac{n}{d}\rfloor \end{array}$$
因而现在只需要枚举 $\mathrm{lcm}(x,y)$ 比 $n$ 小的因子。对 $u,v$ 进行质因子分解，统计 $u$ 的质因子，然后 $2^k$ 枚举所有质因子组合即可。由于 $1\times 10^7$ 下至多只有 $8$ 个质因子，$\mathrm{lcm}(x,y)$最多能包含的本质不同的质因子只有 $12$ 个，因而完全可以通过。总复杂度 $\mathcal{O}(q{2}^k)$，其中 $k\le 12$。

#include 
using namespace std;
const int N = 1e7 + 5;
bool vis[N + 5];
int tot, prime[N + 5], mu[N + 5], minfactor[N + 5];
void sieve(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n;i++)
    {
        if(!vis[i])
        {
            minfactor[i] = i;
            prime[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && (long long)prime[j] * i <= n;j++)
        {
            int num = prime[j] * i;
            vis[num] = 1;
            mu[num] = -mu[i];
            minfactor[num] = minfactor[i];
            if (i % prime[j] == 0)
            {
                mu[num] = 0;
                break;
            }
        }
    }
}
int q, n, m, u, v, ans;
vector<int> factor;
void fac(int x)
{
    while (x > 1)
    {
        factor.push_back(minfactor[x]);
        x /= minfactor[x];
    }
}
void dfs(int step, long long val)
{
    if (val > n)
        return;
    if (step == m)
    {
        ans += mu[val] * (n / val);
        return;
    }
    dfs(step + 1, val * factor[step]);
    dfs(step + 1, val);
}
int main()
{
    sieve(N);
    scanf("%d%d", &n, &q);
    while(q--)
    {
        scanf("%d%d", &u, &v);
        int d = __gcd(u, v);
        if (d == 1)
        {
            printf("1 1\n");
            continue;
        }
        printf("2 ");
        factor.clear();
        fac(u), fac(v);
        sort(factor.begin(), factor.end());
        factor.erase(unique(factor.begin(), factor.end()), factor.end());
        m = factor.size();
        ans = 0;
        dfs(0, 1);
        printf("%d\n", ans + (d == 2));
    }
    return 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
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

J Sum Plus Product

题意：给定长度为 $n$ 的序列 { a i } \{a_i\} {ai​}，每次等概率随机选择两个数字 $a,b$，将它们从序列中删除，并添加 $ab+a+b$，问最终得到数字的期望。$n\le 500$。

解法：整个序列的 $\prod _{i=1}^n(a_i+1)$ 在除了最后一次操作的时候是不会变的，最后一次操作会让它减少 $1$，因而输出 $\prod _{i=1}^n(a_i+1)-1$ 即可。

K The Alchemist of the Discrete Mathematics

题意：给定质数 $p$，问 ${\mathbb{F}}_p$ 中有多少个集合 $S$ 满足存在一个域上 $n$ 次可约多项式 $f(x)=g(x)k(x)$，且 $S=T\cap {\mathbb{F}}_p$，其中 $T$ 为模意义方程 $f(x)g(cx)\equiv 0(\mathrm{mod}p)$ 的解集。$p\le 5\times 10^5$，$n$ 无限制，$c\in {\mathbb{F}}_p$。

解法：显然在 $c$ 的作用下，${\mathbb{F}}_p$ 被分成了 $\frac{p-1}{\mathrm{ord}(c)}$ 个长度为 $\mathrm{ord}(c)$ 的环，和 $0$ 构成的自环。由于 $c$ 的作用，选择了 $x$ 就可以顺带选择 $c^{-1}x$（环上下一个点）。因而对于 $h(x)$ 上连续 $l$ 个零点，只需要 $\lceil \frac{l}{2}\rceil$ 个 $f(x)$ 零点即可——若需要连续的 $x_1,x_2$，其中 $x_1=c{x}_2\mathrm{mod}p$，则可以让 $x-x_1|g(x)$，这样 $x_2$ 就为 $g(cx)$ 的根。因而该问题可以等价于环上选择若干个不相邻的点的方案数，为 $\left(\genfrac{}{}{0ex}{}{n-s}{s}\right)+\left(\genfrac{}{}{0ex}{}{n-s-1}{s-1}\right)$，其中 $n$ 为环长，$s$ 为 $f(x)$ 的根（不相邻点数目）。最后还原到 $h(x)$ 的根的选择，即是这 $s$ 个后续节点（因为在选择不相邻点的时候，是将该点与下一个点绑定了）可选可不选。同时需要特判 $n=2s$ 与 $n=2s-1$ 这两种情况：对于 $n=2s$，朴素选点只有两种选法，但是这两种选法下全选方案其实是一样的，需要减掉一种；对于 $n=2s-1$，在环上选点方案为 $0$，但是其实有一种，且仅有一种：$f(x)$ 选择 $1,3,5\cdots ,n$，对应于 $h(x)$ 的全选。因而最后可以得到的 $f(x)$ 中选择 $s$ 个零点，对应于 $h(x)$ 的零点方案数为 $2^s\left(\left(\genfrac{}{}{0ex}{}{n-s}{s}\right)+\left(\genfrac{}{}{0ex}{}{n-s-1}{s-1}\right)\right)-[n=2s]+[n+1=2s]$。

考虑 $k$ 个环，即是使用生成函数做 $k$ 次幂即可。最后选择不超过 $n$ 个 $f(x)$ 的根，因为对于域上的多项式，任意次幂均有不可约多项式。此处需要它不能产生 ${\mathbb{F}}_p$ 上的根，那么如果仅选择了 $m$ 个零点，只需要找一个 $n-m$ 次的不可约多项式即可，此处 $n-m\ge 2$，因为一次不可约多项式可以产生 ${\mathbb{F}}_p$ 上的根。

int get_ord(int p, int c)
{
    int val = 1, ord = 0;
    while (!ord || val != 1)
    {
        ord++;
        val = 1ll * val * c % p;
    }
    return ord;
}
long long cal(int n, int s)
{
    int ans = th[s] * (C(n - s, s) + C(n - s - 1, s - 1)) % P;
    if (n + 1 == 2 * s)
        inc(ans, 1);
    if (n == 2 * s)
        dec(ans, 1);
    return ans;
}
int main()
{
    th[0] = 1;
    for (int i = 1; i < L;i++)
        th[i] = th[i - 1] * 2 % P;
    printf("%d %d\n", cal(4, 2), cal(7, 4));
    int t, n, p, c;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d", &p, &c, &n);
        int len = get_ord(p, c), cnt = (p - 1) / len;
        Poly f(p + 1, 0);
        for (int i = 0; i <= (len + 1) / 2;i++)
            f[i] = cal(len, i);
        Poly g = f.power(p + 1, cnt);
        int ans = 0;
        for (int i = 0; i <= min(p, n);i++)
        {
            inc(ans, g[i]);
            if (i)
                inc(ans, g[i - 1]);
        }
        if (n == 1)
            dec(ans, 1);
        printf("%d\n", ans);
    }
    return 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
41
42
43
44
45
46
47
48