概要

比赛地址

2020 Multi-University Training Contest 6

题目

1007. A Very Easy Math Problem

题目大意

给定 t, k, x (1\le t\le 10^4,1\le k,x\le 10^9)，计算 t 组 n(1\le n\le 2\cdot 10^5)的函数值：

\sum_{a_1=1}^{n}\cdots \sum_{a_x=1}^{n} \prod_{j=1}^x a_j^k \cdot f(\gcd(a_1,\cdots ,a_x))\gcd(a_1,\cdots ,a_x)

其中 f(x)=|\mu(x)| 。

解题思路

枚举 gcd(a_1,\cdots ,a_x)=d ：

\begin{aligned}
&=\sum_{d=1}^{n}\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}\cdots\sum_{a_x=1}^{n}\left(\prod_{j=1}^{x}{a_j}^{k}\right)\cdot f(d)\cdot [gcd(a_1,\cdots ,a_x)=d]\cdot d\cr
&=\sum_{d=1}^{n}f(d)\cdot d^{kx+1}\sum_{a_1=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{a_2=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\cdots \sum_{a_x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left(\prod_{j=1}^{x}{a_j}^{k}\right)\cdot [gcd(a_1,\cdots ,a_x)=1]\cr
\end{aligned}

又有设：

\begin{aligned}
h(n)&=\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}\cdots\sum_{a_x=1}^{n}\left(\prod_{j=1}^{x}{a_j}^{k}\right)\cdot[gcd(a_1,\cdots ,a_x)=1]\cr
&=\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}\cdots\sum_{a_x=1}^{n}\left(\prod_{j=1}^{x}{a_j}^{k}\right)\cdot\sum_{p|gcd(a_1,\cdots,a_x)}\mu(p)\cr
&=\sum_{p=1}^{n}\sum_{a_1=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum_{a_2=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\cdots \sum_{a_x=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\left(\prod_{j=1}^{x}{\left(a_j\cdot p\right)}^{k}\right)\cdot \mu(p)\cr
&=\sum_{p=1}^{n}p^{kx}\cdot\mu(p)\cdot\left(\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}i^k\right)^x
\end{aligned}

令：

S(n)=\left(\sum_{i=1}^{n}i^k\right)^x

则：

h(n)=\sum_{p=1}^{n}p^{kx}\cdot\mu(p)\cdot S\left(\left\lfloor\frac{n}{p}\right\rfloor\right)

所以原式：

\begin{aligned}
&=\sum_{d=1}^{n}f(d)\cdot d^{kx+1}\cdot h\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\cr
&=\sum_{d=1}^{n}f(d)\cdot d^{kx+1}\cdot \sum_{p=1}^{\left\lfloor\frac{n}{d}\right\rfloor}p^{kx}\cdot\mu(p)\cdot S\left(\left\lfloor\frac{n}{pd}\right\rfloor\right)
\end{aligned}

枚举 T=pd：

\begin{aligned}
&=\sum_{T=1}^{n}S\left(\left\lfloor\frac{n}{T}\right\rfloor\right)\cdot\sum_{p|T}p^{kx}\cdot\mu(p)\cdot f\left(\frac{T}{p}\right)\cdot \left(\frac{T}{p}\right)^{kx+1}\cr
&=\sum_{T=1}^{n}S\left(\left\lfloor\frac{n}{T}\right\rfloor\right)\cdot\left(\sum_{p|T}\mu(p)\cdot \left(\mu\left(\frac{T}{p}\right)\right)^2\cdot \frac{T}{p}\right)\cdot T^{kx}
\end{aligned}

令：

g(T)=\left(\sum_{p|T}\mu(p)\cdot \left(\mu\left(\frac{T}{p}\right)\right)^2\cdot \frac{T}{p}\right)\cdot T^{kx}

则原式：

=\sum_{T=1}^{n}S\left(\left\lfloor\frac{n}{T}\right\rfloor\right)\cdot g(T)

对于全部的 g(T)，我们可以从 1 到 n 枚举因子 p，对于其全部的倍数进行处理，复杂度 O(nlogn)；我们可以线性筛出 \mu(i) 和 S(i)。预处理总体复杂度 O(nlogn)。对于每组询问，只需要整除分块即可，复杂度 O(T\sqrt n)。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 50;
const int P = 1e9 + 7;
int T, n, k, x;

int ksm(int a, ll b, int c) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % c) {
        if (b & 1) {
            ret = 1LL * ret * a % c;
        }
    }
    return ret;
}

int prime[N], num[N], mu[N], tot;
void getmu() {
    mu[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!num[i]) {
            prime[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && i * prime[j] < N; j++) {
            num[i * prime[j]] = 1;
            if (i % prime[j]) {
                mu[i * prime[j]] = -mu[i];
            }
            else {
                break;
            }
        }
    }
}
long long g[N], sumg[N];
void getg() {
    for (int i = 1; i < N; i++) {
        for (int j = 1; i * j < N; j++) {
            g[i * j] += mu[i] * mu[j] * mu[j] * j;
        }
    }
    for (int i = 1; i < N; i++) {
        int tmp = ksm(i, 1LL * k * x, P);
        g[i] = (g[i] + P) % P * tmp % P;
    }
    for (int i = 1; i < N; i++) {
        sumg[i] = (sumg[i - 1] + g[i]) % P;
    }
}
int s[N];
void gets() {
    for (int i = 1; i < N; i++) {
        s[i] = (s[i - 1] + ksm(i, k, P)) % P;
    }
    for (int i = 1; i < N; i++) {
        s[i] = ksm(s[i], x, P);
    }
}
void init() {
    getmu();
    getg();
    gets();
}
int work() {
    int ret = 0;
    for (int i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i);
        (ret += 1LL * s[n / i] * (sumg[j] - sumg[i - 1] + P) % P) %= P;
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    scanf("%d%d%d", &T, &k, &x);
    init();
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", work());
    }
    return 0;
}

1008. Yukikaze and Smooth numbers

题目大意

给定 n,k。一个正整数，当且仅当它所有质因数都小于等于 k 时，视为合法。求有多少小于等于 n 的合法的正整数。一共 T 组数据，1\le T\le 50，1\le n,k \le 10^9。

解题思路

我们分类讨论。

当 n \le k 时，全部 n 个数均可，答案为 n;

当 k^2\ge n 时，我们可以枚举最大因子 x(x>k)。n 以内最大因子为 x 的数的个数为 \left\lfloor\frac{n}{x}\right\rfloor，因此答案为：

ans=n-\sum_{i=k+1}^{n}[i\in prime]\left\lfloor\frac{n}{i}\right\rfloor

我们可以对这个式子整除分块，唯一的难点在于求块中有多少个质数。这个问题可以使用 min25 筛来解决：
首先使用 min25 筛算出 [1,k] 的质数个数，记为 lst。对于每次整除分块，我们要求 [l,n/(n/l)] 的质数个数：

val[m]=n/(n/l);

\begin{cases}
id1[n/(n/l)]=m,&n/(n/l)\le lim\cr id2[n/(n/(n/l))]=id2[n/l]=m,&n/(n/l)>lim
\end{cases}

g[m]=(n/(n/l)\ 以内质数点值之和)

可见我们只需要预处理一次 n 的和一次 k 的 min25 筛，就可以 O(1) 得到 j 以内的质数个数。用 j-lst 可得到块内质数个数，再将 j 赋值给 lst 可继续迭代更新。
复杂度为 O(\frac{n^{3/4}}{logn})。

当 k^{2}<n 时，注意到 k 的上界在 3\cdot 10^4 左右。我们可以暴力dfs：枚举所有小于等于 k 的质数，以及选了多少次。这里需要几个剪枝：

• 当前乘积乘以当前质数大于 n，则直接停止搜索，答案+1（啥都不乘）；
• 当前乘积乘以当前质数的平方大于 n，说明至多只能再乘一个质数，可以二分搜索所有剩余的质数；

AC代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 50;
ll n, k;

int num[N], prime[N], tot;
void init() {
    for( int i = 2; i < N; i++) {
        if(!num[i]) prime[++tot] = i;
        for(int j = 1, x; j <= tot && (x = prime[j] * i) < N; j++) {
            num[x] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

struct Min25 {
    ll g[N << 1], id1[N << 1], id2[N << 1], val[N << 1];
    ll n, lim, sp[N];

    void init() {
        for (int i = 1; i <= tot; i++) {
            sp[i] = sp[i - 1] + 1;
        }
    }
    void build(ll _n) {
        n = _n; lim = sqrt(n);
        int m = 0;
        for(ll l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            val[++m] = n / l;
            if (val[m] <= lim) id1[val[m]] = m;
            else id2[n/val[m]] = m;
            g[m] = val[m] - 1;
        }
        for (int j = 1; j <= tot; j++) {
            for (int i = 1; 1LL * prime[j] * prime[j] <= val[i]; i++) {
                ll tmp = val[i] / prime[j];
                if (tmp <= lim) tmp = id1[tmp];
                else tmp = id2[n / tmp];
                g[i] -= g[tmp] - sp[j - 1];
            }
        }
    }
    ll solve(ll l) {
        if (n / (n / l) <= lim) return g[id1[n / (n / l)]];
        return g[id2[n / l]];
    }
}Sn, Sk;

int ret, lim;
void dfs(int i, ll prd) {
    if (i == lim || prd * prime[i] > n) {
        ret++; return;
    }
    if (prd * prime[i] * prime[i] > n) {
        int l = i, r = lim;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (prd * prime[mid] <= n) l = mid;
            else r = mid;
        }
        ret += l - i + 2;
        return;
    }
    for (ll x = 1; ; x *= prime[i]) {
        if (x * prd > n) break;
        dfs(i + 1, x * prd);
    }
}

int main() {
    init();
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &n, &k);
        if (k >= n) {
            printf("%lld\n", n); continue;
        }
        if (k * k >= n) {
            Sk.init(); Sk.build(k);
            ll lst = Sk.g[1];
            Sn.init(); Sn.build(n);
            ll ans = 0;
            for (ll i = k + 1, j; i <= n; i = j + 1) {
                j = n / (n / i);
                ll tmp = Sn.solve(i);
                ans += (n / i) * (tmp - lst);
                lst = tmp;
            }
            printf("%lld\n", n - ans);
            continue;
        }
        ret = 0;
        lim = int(upper_bound(prime + 1, prime + 1 + tot, k) - prime);
        dfs(1, 1);
        printf("%d\n", ret);
    }
    return 0;
}

1010. Expectation

题目大意：

给一张 n 个点 m 条边的图。定义生成树权值为所有边权的与。问随机选取一棵生成树的权值期望。

解题思路：

首先考虑图中的生成树个数，我们可以直接给所有边权赋值为 1 后使用矩阵树定理得出；

再考虑拆位计算全部生成树的贡献。对于第 x 位，我们只保留该位边权为 1 的边。得到生成树的个数后，乘以 1<<x 即为这一位的贡献。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) {
            ret = 1LL * ret * a % P;
        }
    }
    return ret;
}
int ni(int a) {
    return ksm(a, P - 2);
}

struct Matrix {
    int n, m;
    vector< vector<int> > a;
    void clear() {
        vector<int> tmp(m + 1);
        a.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            a[i] = tmp;
        }
    }
    Matrix(int _n, int _m) : n(_n), m(_m) {
        clear();
    }
    Matrix(int _n) : n(_n), m(_n) {
        clear();
    }
    Matrix() {}

    void rswap(int x, int y) {
        swap(a[x], a[y]);
    }
};

int det(Matrix A) {
    int n = A.n, ret = 1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!A.a[i][i]) {
            for(int j = i + 1; j <= n; j++) if (A.a[j][i]) {
                A.rswap(i, j); cnt++; break;
            }
        }
        if (!A.a[i][i]) continue;
        for (int j = i + 1; j <= n; j++) {
            int t = 1LL * A.a[j][i] * ni(A.a[i][i]) % P;
            for (int k = i; k <= n; k++) {
                (A.a[j][k] += P - 1LL * t * A.a[i][k] % P) %= P;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ret = 1LL * ret * A.a[i][i] % P;
    }
    return ret;
}

int Matrix_Tree(Matrix A, int rt = 0) {
    int n = A.n;
    if (!rt) rt = n;
    for (int i = rt; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            A.a[i][j] = A.a[i + 1][j];
        }
    }
    for (int j = rt; j < n; j++) {
        for (int i = 1; i <= n; i++) {
            A.a[i][j] = A.a[i][j + 1];
        }
    }
    A.a.pop_back(); A.n = A.m = n - 1;
    for (int i = 0; i < n; i++) A.a[i].pop_back();
    return det(A);
}

const int N = 1e4 + 50;
int tot;
struct Edge {
    int u, v, w;
}e[N];

int main(int argc, const char * argv[]) {
    int T, n, m; scanf("%d", &T);
    while (T--) {
        tot = 0;
        scanf("%d%d", &n, &m);
        Matrix A(n);
        for (int i = 1, u, v, w; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            e[++tot] = (Edge) {u, v, w};
            A.a[u][u]++; A.a[v][v]++;
            (A.a[u][v] += P - 1) %= P;
            (A.a[v][u] += P - 1) %= P;
        }
        int base = Matrix_Tree(A);
        long long all = 0;
        for (int i = 0, x = 1; i <= 30; i++, x <<= 1) {
            A.clear();
            for (int j = 1; j <= m; j++) {
                int u = e[j].u, v = e[j].v, w = e[j].w;
                if ((w >> i) & 1) {
                    A.a[u][u]++; A.a[v][v]++;
                    (A.a[u][v] += P - 1) %= P;
                    (A.a[v][u] += P - 1) %= P;
                }
            }
            all += 1LL * Matrix_Tree(A) * x % P;
        }
        int ans = all % P * ni(base) % P;
        printf("%d\n", ans);
    }
    return 0;
}