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

被完虐... QwQ

#T1

#Problem

给定 $n,p$，求：

$$\sum _{i=1}^n\sum _{j=1}^p\phi (i^j)\mathrm{mod}{10}^9+7.$$

#Solution

#60pts

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

$$\begin{array}{rl}& \sum _{i=1}^n\sum _{j=1}^p\phi (i^j)=\sum _{i=1}^n\sum _{j=1}^p\sum _{d|i^j}\mu (d){\displaystyle \frac{i^j}{d}}\\ =& \sum _{d=1}^n\mu (d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^p{i}^j{d}^{j-1}=\sum _{j=1}^p\sum _{d=1}^n\mu (d)d^{j-1}\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }{i}^j\end{array}$$

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

#100pts

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

$$\phi (i^j)=\phi (i)\cdot i^{j-1}$$

于是原式化为

$$\begin{array}{rl}& \sum _{i=1}^n\sum _{j=1}^p\phi (i^j)=\sum _{i=1}^n\sum _{j=1}^p{i}^{j-1}\phi (i)=\sum _{i=1}^n\phi (i)\sum _{j=1}^p{i}^{j-1}\\ =& p\cdot \phi (1)+\sum _{i=2}^n\phi (i){\displaystyle \frac{i^p-1}{i-1}}=p\cdot \phi (1)+\sum _{i=2}^n{\displaystyle \frac{1}{i-1}}\phi (i)(i^p-1)\\ =& p\cdot \phi (1)+\sum _{i=2}^n{\displaystyle \frac{1}{i-1}}(\phi (i)\cdot i^p-\phi (i))\end{array}$$

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

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

#Code

#60pts

#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

#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$，要求 $\mathrm{\forall }a\in S$，值 $a$ 对应的节点是叶结点。求有多少个满足要求的大根堆，答案 $mod{10}^9+7$。

#Solution

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

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

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

#Code

#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$$

记该序列为 $\{mx{l}_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^{\prime },k-1}$ 其中 $j^{\prime }>j$，因为不合法的状态我们已经设置为 $0$，所以可以放心转移。用前缀和优化，可以做到 O(Tn^4)。

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

#Code

#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

#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$ 没想到还骗过了一个点（