首页 模拟赛

整除分块 + 莫比乌斯函数，点分树 + 可持久化可并堆，多项式（拉格朗日插值）+ dp

# A. 《如何优雅地送分》

考场上只会 30pts /kk

题目要求 ∑i=1n2F(i)\sum\limits_{i = 1}^n2^{F(i)}，F(i)F(i) 为 ii 的不同的质因子个数。

然后就是喜闻乐见的推式子：

∑i=1n2F(i)=∑i=1n∑d∣iμ2(d)=∑i=1n∑d∣i∑k2∣dμ(k)=∑k2=1nμ(k)∑k2∣d⌊nd⌋=∑k2=1nμ(k)∑i=1⌊nk2⌋⌊nk2i⌋=∑k2=1nμ(k)S(⌊nk2⌋)\begin{aligned} \sum_{i = 1}^n2^{F(i)} = & \sum_{i = 1}^n\sum_{d \mid i}\mu^2(d) \\ =& \sum_{i = 1}^n\sum_{d \mid i}\sum_{k^2 \mid d} \mu(k) \\ =& \sum_{k^2 = 1}^n\mu(k)\sum_{k^2 \mid d}\lfloor\frac nd\rfloor \\ =& \sum_{k^2 = 1}^n\mu(k)\sum_{i = 1}^{\lfloor\frac n{k^2}\rfloor}\lfloor\frac n{k^2i}\rfloor \\ =& \sum_{k^2 = 1}^n\mu(k)S(\lfloor\frac n{k^2}\rfloor) \end{aligned}

S(n)=∑i=1n⌊ni⌋S(n) = \sum\limits_{i = 1}^n \lfloor\frac ni \rfloor. 可以使用整除分块快速计算，总复杂度 O(nln⁡n)O(\sqrt n\ln n)

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int n, ans;
int mu[N], p[N], tot;
bool vis[N];

inline void euler(int n){
    mu[1] = 1;
    for(int i = 2; i <= n; ++i){
        if(!vis[i]) mu[i] = -1, p[++tot] = i;
        for(int j = 1; j <= tot && i * p[j] <= n; ++j){
            vis[i * p[j]] = 1;
            if(i % p[j] != 0) mu[i * p[j]] = -mu[i];
            else {mu[i * p[j]] = 0; break;}
        }
    }
}

inline int calc(int n){
    int res = 0;
    for(int l = 1, r; l <= n; l = r + 1){
        r = n / (n / l);
        res = (res + (r - l + 1) * (n / l) % mod) % mod;
    }
    return res;
}

signed main(){
    n = read();
    euler(sqrt(n));
    for(int i = 1; i * i <= n; ++i) ans = (ans + mu[i] * calc(n / i / i) % mod + mod) % mod;
    write(ans), puts("");
    return 0;
}
// X.K.

# B. 《阴阳》

阴阳题。

可持久化点分树，然而思路太过神仙，std 也太过神仙，咕咕咕。

暴力 set\text{set} 维护可得 60pts 的好成绩。

# C. 《你猜是不是找规律》

正解：打表找规律

好吧确实是要打个表找找规律的，可以找出 O(nk)O(nk) 的递推式，设 fi,jf_{i, j} 表示长度为 ii 的排列，恰好交换 jj 次能使之有序的排列数：

fi,j=(i−1)×fi−1,j−1+fi−1,jf_{i, j} = (i - 1) \times f_{i - 1, j - 1} + f_{i - 1, j}

感性理解一下，fn,kf_{n, k} 是关于 nn 的 2k+12k + 1 次多项式，然后拉插一下即可（

这里讲一下 zzzzzz 神仙的神仙做法。

从一个乱序排列变成有序排列里面有许多置换环。

如果一个置换环的长度为 kk，那么我们需要 k−1k - 1 次交换来使这个环上的数都到它应该在的位置。

此时我们有 tt 个环，那么总点数为 t+kt + k，从 nn 里面任意选 t+kt + k 个数，就是 (nt+k)\dbinom{n}{t + k}。

然后我们要把这 t+kt + k 个数变成有序的，需要再乘上 ft+k,kf_{t + k, k}。

需要注意的一点：我们找的置换环长度必须严格大于 1，所以转移略有不同，具体来说，把 fi−1,jf_{i - 1, j} 这一项改为 (i−1)×fi−2,j−1(i - 1) \times f_{i - 2, j - 1}。

也就是从前 ii 个数中招至少 2 个数放到第 jj 个环里，有 i−1i - 1 种选择。

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
#include <bits/stdc++.h>
#define ll long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 3e3 + 10;
const int mod = 1e9 + 7;
int n, k;

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

int s[N << 1][N], f[N << 1], ifac[N << 1];

signed main(){
    n = read(), k = read();
    s[0][0] = 1;
    for(int i = 2; i <= 2 * k; ++i)
        for(int j = 1; j <= k; ++j)
            s[i][j] = (1ll * (i - 1) * s[i - 1][j] % mod + 1ll * (i - 1) * s[i - 2][j - 1] % mod) % mod;
    f[1] = n, ifac[0] = ifac[1] = 1;
    for(int i = 2; i <= 2 * k; ++i)
        f[i] = 1ll * f[i - 1] * (n - i + 1) % mod, ifac[i] = 1ll * ifac[i - 1] * qpow(i, mod - 2) % mod;
    int res = 1;
    for(int i = 1; i <= k; ++i)
        for(int j = 1; j <= k; ++j)
            res = (res + 1ll * f[i + j] * ifac[i + j] % mod * s[i + j][i] % mod) % mod;
    write(res), puts("");
    return 0;
}
// X.K.
// s[1][0] = 1;
// for(int i = 1; i <= n; ++i) s[i][0] = 1;
// for(int i = 2; i <= n; ++i)
//     for(int j = 1; j < i; ++j)
//         s[i][j] = ((i - 1) * s[i - 1][j - 1] % mod + s[i - 1][j]) % mod;
// int ans = 0;
// for(int i = 0; i <= k; ++i) ans = (ans + s[n][i]) % mod;
// write(ans), puts("");
// return 0;

阅读次数 次