「考试总结」ZROI-21-NOIP10连-DAY1 总结

发表于 更新于 分类于
ZROI-21-NOIP10连-DAY1 总结

被完虐... QwQ

#T1

#Problem

给定 \(n,p\)，求：

\[ \sum\limits_{i=1}^n\sum\limits_{j=1}^p\varphi(i^j)\mod 10^9+7. \]

#Solution

#60pts

考场上最初以为是莫比乌斯反演的题，先简单推一推：

\[ \begin{aligned} &\sum\limits_{i=1}^n\sum\limits_{j=1}^p\varphi(i^j)=\sum\limits_{i=1}^n\sum\limits_{j=1}^p\sum\limits_{d|i^j}\mu(d)\dfrac{i^j}{d}\\ =&\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^pi^jd^{j-1}=\sum\limits_{j=1}^p\sum\limits_{d=1}^n\mu(d)d^{j-1}\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}i^j \end{aligned} \]

推到这里，我已经做不下去了，这样的时空复杂度可以做到 \(O(np)\)，可得 \(60pts\)，注意到，这里无法继续进行的原因是幂没有合适的处理方法。

#100pts

接着上面的错误思路返回原点，突然想起欧拉函数具有以下性质：

\[ \varphi(i^j)=\varphi(i)\cdot i^{j-1} \]

于是原式化为

\[ \begin{aligned} &\sum\limits_{i=1}^n\sum\limits_{j=1}^p\varphi(i^j)=\sum\limits_{i=1}^n\sum\limits_{j=1}^pi^{j-1}\varphi(i)=\sum\limits_{i=1}^n\varphi(i)\sum\limits_{j=1}^pi^{j-1}\\ =&p\cdot\varphi(1)+\sum\limits_{i=2}^n\varphi(i)\dfrac{i^p-1}{i-1}=p\cdot\varphi(1)+\sum\limits_{i=2}^n\dfrac{1}{i-1}\varphi(i)(i^p-1)\\ =&p\cdot\varphi(1)+\sum\limits_{i=2}^n\dfrac{1}{i-1}\left(\varphi(i)\cdot i^p-\varphi(i)\right) \end{aligned} \]

对于后面的和式，不难发现 \(\varphi\) 是积性函数，\(i^p\) 是完全积性函数，于是我们便可以用线性筛筛出这两个函数，其中在 \(i\) 为质数时，\(i^p\) 需要使用一次快速幂，而小于等于 \(n\) 的质数个数 \(\pi(n)\) 约为 \(\dfrac{n}{\ln n}\)，于是线性筛的整体时间复杂度约为 \(O(n\log_np)\)，可以接受。

我们再线性推个逆元，直接求和即得答案。

#Code

#60pts

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
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int M = 10010;
const int N = 10000010;
const ll MOD = 1e9 + 7;
const int INF = 0x3fffffff;

int n, p, nprm[N], prm[N], pcnt;
ll mi[M][M], mu[N], sum[M][M], ans, sum1[N];

inline ll fpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) (res *= a) %= MOD;
        (a *= a) %= MOD; b >>= 1;
    }
    return res;
}

void euler(int x) {
    mu[1] = 1;
    for (int i = 2; i <= x; i ++) {
        if (!nprm[i]) prm[++ pcnt] = i, mu[i] = -1;
        for (int j = 1; j <= pcnt; j ++) {
            if (prm[j] * i > x) break;
            nprm[prm[j] * i] = true;
            if (i % prm[j]) mu[i * prm[j]] = -mu[i];
            else break;
        }
    }
}

signed main() {
    scanf("%lld%lld", &n, &p); euler(n);
    if (p == 1) {
        for (int i = 1; i <= n; ++ i)
          sum1[i] = (sum1[i - 1] + i) % MOD;
        for (int d = 1; d <= n; ++ d) {
            ans += mu[d] * sum1[n / d] % MOD;
            (ans += MOD) %= MOD;
        }
          
    } else {
        for (int i = 1; i <= n; ++ i)
          for (int j = 0; j <= p; ++ j) {
            mi[i][j] = fpow(i, j) % MOD;
            sum[i][j] = (sum[i - 1][j] + mi[i][j]) % MOD;
          }
        for (int i = 1; i <= p; ++ i)
          for (int d = 1; d <= n; ++ d) {
              ans += mu[d] * mi[d][i - 1] % MOD * sum[n / d][i] % MOD;
              (ans += MOD) %= MOD; 
          }
    }
    printf("%lld", ans);
    return 0;
}

#100pts

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
#include <bits/stdc++.h>
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int M = 10010;
const int N = 10000010;
const ll MOD = 1e9 + 7;
const int INF = 0x3fffffff;

ll n, p, mu[N], nprm[N], prm[N], pcnt;
ll ans, phi[N], f[N], mi[N], inv[N];

inline ll fpow(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1) (res *= a) %= MOD;
        (a *= a) %= MOD; b >>= 1;
    }
    return res;
}

void euler(int x) {
    phi[1] = 1; f[1] = 1;
    for (int i = 2; i <= x; i ++) {
        if (!nprm[i]) {
            prm[++ pcnt] = i, mi[i] = fpow(i, p);
            phi[i] = i - 1, f[i] = phi[i] * mi[i] % MOD;
        }
        for (int j = 1; j <= pcnt; j ++) {
            if (prm[j] * i > x) break;
            nprm[prm[j] * i] = true;
            if (i % prm[j]) {
                f[i * prm[j]] = f[i] * f[prm[j]] % MOD;
                phi[i * prm[j]] = phi[i] * (prm[j] - 1) % MOD;
            } else {
                phi[i * prm[j]] = phi[i] * prm[j] % MOD;
                f[i * prm[j]] = f[i] * prm[j] % MOD * mi[prm[j]] % MOD;
                break;
            }
        }
    }
}

int main() {
    scanf("%lld%lld", &n, &p);
    euler(n); inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; ++ i) 
      inv[i] = ((MOD - MOD / i) * inv[MOD % i]) % MOD;
    for (int i = 2; i <= n; ++ i)
      (ans += inv[i - 1] * (f[i] - phi[i]) % MOD + MOD) %= MOD;
    printf("%lld", (ans + p % MOD + MOD) % MOD);
    return 0;
}

#T2

巨大诈骗题，赛时想麻烦了（

#Problem

一个含有 \(n\) 个点的大根堆是一个二叉树，左右儿子有区别，每个节点上有一个 \(1\sim n\) 的值，任意两个节点上的值不同，且父亲节点的权值大于子节点的权值。

现在给定一个集合 \(S\)，要求 \(\forall a\in S\)，值 \(a\) 对应的节点是叶结点。求有多少个满足要求的大根堆，答案 \(\bmod 10^9+7\)。

#Solution

首先明确概念：堆不一定是完全二叉树！

“左偏堆是不是堆？左偏堆是完全二叉树吗？” ——wzy

因为是一个大根堆，于是插入顺序可以直接确定为由大到小插入，我们设当前可选位置个数为 \(s\)，不难发现，对于一个必须为叶子的节点，不论放到哪里，下一个点的可选位置一定减少一，如果不是，那么自己占了一个位置，又提供了两个可选位置，于是下一个点的可选位置一定增加一，将每一步的 \(s\) 相乘即得答案。

#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
#include <bits/stdc++.h>
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int N = 1000010;
const ll MOD = 1e9 + 7;
const int INF = 0x3fffffff;

int n,  p, vis[N];
ll s = 1, ans = 1;

int main() {
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= p; ++ i) {
        int x; scanf("%d", &x); vis[x] = 1;
    }
    for (int i = n; i >= 1; -- i) {
        (ans *= s) %= MOD;
        if (vis[i]) -- s; else ++ s;
    }
    printf("%lld", ans);
    return 0;
}

#T3

#Problem

初始有一张含有 \(n\) 个点的有向图，你可以不断向其中加入至多 \(n(n−1)\) 条边，不允许加入重边或者自环。

定义一个长度为 \(m\) 的序列 \(\{ai\}\) 为一个 SCC 序列，当且仅当存在一种加边方案，使得加入 \(i\) 条边后图中恰好存在 \(a_i\) 个强连通分量（两个点在一个强连通分量中当且仅当他们能够相互到达）。

给定 \(n\)，你需要求出当序列长度分别为 \(1\cdots n(n−1)\) 时，有多少种 SCC 序列，由于答案可能很大，需要对于一个数字取模。为了防止打表，模数是输入的。

#Solution

用的 zyc 大佬的思路，这里说的详细一点。

我们考虑这个序列字典序最大是多少，假设 \(n=4\)，那么这个序列是：

\[ 4,4,4,4,4,4,3,2,2,1,1,1 \]

记该序列为 \(\{mxl_i\}\) 我们考虑这个序列是怎么形成的，一开始有 \(n\) 个空点，然后相邻连边，就可以使 scc 个数不变。加的不能加为止，不难发现，每多连一条边，就可以有 \(x\) 条边使得 scc 个数为 \(n−x\) 不变。这个自己画一下图就能论证。

接下来我们考虑如果已知一个前缀 scc 序列，如何看下一个值最小能填多少？我们不难发现，这个数是 \(n−k+1\)，其中 \(n\) 是序列长度，\(k\) 是序列中不同的数的个数。这个很好论证，用构造的方法就可以证明。

至于上界，这个就是上一位和这一位的 \(mxl\) 值做 \(\min\) 就可以。

上下界固定后，暴力就好想了，DP 也很自然。

设 \(f_{i,j,k}\) 表示序列长度为 \(i\)，最后一个数为 \(j\)，有 \(k\) 个不同的数的方案数。

我们考虑有哪些状态可以转移到 \(f_{i,j,k}\)。我们考虑如果这个序列中 \(j\) 不止一个，那么就可以从 \(f_{i−1,j,k}\) 中转移。

否则，我们枚举第 \(i−1\) 个填了什么，然后转移，不难发现这个东西是 \(f_{i−1,j',k−1}\) 其中 \(j'>j\)，因为不合法的状态我们已经设置为 \(0\)，所以可以放心转移。用前缀和优化，可以做到 O(Tn^4)。

空间简单卡一下可以通过，保险起见，这里采用滚动数组优化。

#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
#include <bits/stdc++.h>
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int N = 101;
const int INF = 0x3fffffff;

int f[2][N][N], pre[N][N], MOD, mxl[N * N];

inline void prework(int n) {
    for (int i = 1; i <= n * (n - 1) / 2; ++ i) mxl[i] = n;
    for (int i = n - 1; i; -- i)
      for (int j = (n - i) * (n - i - 1) / 2 + 1; j <= (n - i) * (n - i - 1) / 2 + n - i; ++ j)
        mxl[n * (n - 1) / 2 + j] = i;
}

inline int red(int x) {return x >= MOD ? x - MOD : x;}

inline void solve(int n) {
    mset(f, 0); f[1][n][1] = 1; printf("1 ");
    for (int i = 2; i <= n * (n - 1); ++ i) {
        mset(f[i & 1], 0); int ans = 0;
        for (int j = 1; j <= n && j <= i; ++ j) {
            pre[1][j] = f[!(i & 1)][1][j];
            for (int k = 2; k <= mxl[i - 1]; ++ k)
              pre[k][j] = red(pre[k - 1][j] + f[!(i & 1)][k][j]);
        }
        for (int j = 1; j <= mxl[i]; ++ j)
          for (int k = 1; k <= n && k <= i && k <= (n - j + 1); ++ k) {
              int l = max(j, n - i + k - 1); if (l > j) continue; 
              f[i & 1][j][k] = (pre[mxl[i - 1]][k - 1] - pre[l + (l == j) - 1][k - 1] + MOD) % MOD;
              if (l == j) f[i & 1][j][k] = red(f[i & 1][j][k] + f[!(i & 1)][j][k]);
              ans = red(ans + f[i & 1][j][k]);
          }
        printf("%d ", ans);
    } printf("\n");
}

int main() {
    int T, n; scanf("%d", &T);
    while (T --) {
        scanf("%d%d", &n, &MOD);
        prework(n); solve(n);
    }
    return 0;
}

#T4

#Problem

有一个长度为 \(n\) 的数列 \(a_i\)，Alice 和 Bob 手上分别有一个初始为 \(0\) 的数字（分别记为 \(A,B\)）。Alice 和 Bob 轮流做如下操作：

  • 从序列开头或者结尾取出一个数 \(x\)，让自己手上的数字异或上 \(x\)，并把 \(x\) 从序列中删除。

Alice 先手，最后谁手上的数字大谁就胜了。如果 Alice,Bob 均使用最优策略，那么谁能取胜？（或者平局，即两个人手上的数字一样大）

#Solution

首先不难发现，当 \(a_i\) 的异或和为 \(0\) 时一定为平局，否则 \(s\) 在二进制下最高的非零位 \(p\) 必然是决胜的关键，于是我们便可以将原本的 \(a_i\) 按照第 \(p\) 位是否为 \(1\) 转变为 01 序列，下面的操作都是在 01 序列上进行的讨论。

分为两种情况：长度为奇数和长度为偶数。

先来看第一种：长度为偶数。我们将 01 序列分为奇数位和偶数位，此时 a_i 的异或和不为 \(0\)，所以必然要么是奇数位上有奇数个 \(1\)，要么是偶数位上有奇数个 \(1\)，于是先手可以直接控制后手所选的 \(1\) 的奇偶性，故在此种情况下先手必胜。

再来看长度为奇数的情况：

  • 假如两端都是 \(0\)，那么无论先手选哪个都会使当前后手变为长度为偶数的先手状态，于是此时先手必败；

  • 假如一端为 \(1\)，那么先手必然要选作为 \(1\) 的一端，否则必败，不是最优策略；之后先手需要跟随后手的选择，保证两者的选择完全一致，否则必败我们来简单讨论一下原因：

    • 假如在这一步之前，所有的先手的每一步都跟随着后手选，所以此时先后手选的 \(1\) 的数量的奇偶性一定不同，在这一步时，后手选了 \(1\)，先手选了 \(0\)，那么此时先后手选的 \(1\) 的数量的奇偶性变为相同，于是一共选了偶数个 \(1\)，还剩奇数个 \(1\)，此时一共选了奇数个数字，于是还剩偶数个数字，此时后手作为当前局面的先手进入必胜状态；于是这样选先手必败。
    • 在这一步时，后手选了 \(0\)，先手选了 \(1\)，与上面的证明同理，可得这样先手必败。

    由于先手取走了一个 \(1\)，那么此时 \(1\) 的个数为偶数，由于每一步先手都跟着后手选，所以先后手必然平分偶数个 \(1\)，如果这个个数不能被 \(4\) 整除，也就意味着先手被分到了奇数个 \(1\)，加上了最初的那个 \(1\)，必败。

那么，怎样的序列才能满足先手能跟着后周的每一步选呢？删除掉左右两边相同的数后，剩下的应当满足相邻奇偶位（如 \(1\) 和 \(2\) 是，但 \(2\) 和 \(3\) 不是）上的数字相同，这里不证正确性，证法与上面相似。

#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
#include <bits/stdc++.h>
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int N = 200010;
const int INF = 0x3fffffff;

int a[N], s, n, T, l, r, p, tot;

inline bool check(int l, int r, int cnt) {
    while (l < r && a[l] == a[r]) ++ l, -- r;
    while (l < r && a[l] == a[l + 1]) l += 2;
    if (l < r) return 0; else return 1;
}

int main() {
    scanf("%d", &T);
    while (T --) {
        scanf("%d", &n); l = 1, r = n;
        p = 30, tot = 0, s = 0;
        for (int i = 1; i <= n; ++ i)
          scanf("%d", &a[i]), s ^= a[i];
        if (!s) {printf("Draw\n"); continue;}
        if (!(n & 1)) {printf("Alice\n"); continue;}
        while (p && !((s >> p) & 1)) -- p;
        for (int i = 1; i <= n; ++ i)
          a[i] = (a[i] >> p) & 1, tot += a[i];
        if (a[1] == 0 && a[n] == 0) {printf("Bob\n"); continue;}
        -- tot; if (tot % 4) {printf("Bob\n"); continue;}
        if ((a[1] && check(2, n, tot)) || (a[n] && check(1, n - 1, tot)))
          printf("Alice\n");
        else printf("Bob\n");
    }
    return 0;
}

期望得分：\(100+20+0+0=120\) 实际得分：\(100+30+0+0=130\) 没想到还骗过了一个点（