组队训练赛（二）

组队训练赛（二）¶

题目1¶

题目链接¶

题目描述¶

You are given an integer n. Please output the answer of modulo 998244353. n is represented in the form of factorization.

φ(n) is Euler’s totient function, and it is defi ned more formally as the number of integers k in the interval 1≤k≤n for which the greatest common divisor gcd(n,k) is equal to 1.

For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all co-prime to 9, but the other three numbers in this interval, 3, 6, and 9 are not, because gcd(9,3) = gcd(9,6) = 3 and gcd(9,9) = 9.

Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the interval from 1 to n is 1 itself, and gcd(1,1) = 1.

And there are several formulas for computing φ(n), for example, Euler’s product formula states like:

where the product is all the distinct prime numbers (p in the formula) dividing n.

输入¶

The fi rst line contains an integer T (1≤T≤20) representing the number of test cases.

For each test case, the fi rst line contains an integer m(1≤m≤20) is the number of prime factors.

The following m lines each contains two integers pi and qi (2≤pi≤108 , 1≤qi≤108 ) describing that n contains the factor piqi , in other words, . It is guaranteed that all pi are prime numbers and diff erent from each other.

输出¶

For each test case, print the the answer modulo 998244353 in one line.

样例输入¶

样例输出¶

15
168

提示¶

For first test case, n = 21*31= 6, and the answer is (φ(1)*n/1+φ(2)*n/2+φ(3)*n/3+φ(6)*n/6) mod 998244353 = (6 + 3 + 4 + 2) mod 998244353 = 15.

题解¶

题目要求求解 $F(n)=\sum_{d|n} \varphi(d)*\frac{n}{d}$ ，由于欧拉函数和 $\frac{n}{d}$ 均为积性函数，则有

$F(m*n)=F(m)*F(n)$

即为 $F( \prod p_i^{q_i})=\prod F(p_i^{q_i})$ ，则

$F(p_i^{q_i})=\sum_{d|n}\varphi(d)*\frac{n}{d}=\varphi(1)*n+\sum_{i=1}^{q} \varphi(p^i)*\frac{n}{p^i}=p_i^{q_i}+\sum _{i=1} ^{q_i}(p_i-1)*(p_i^{i-1}*\frac{p_i^{q_i}}{p_i})$

$=p_i^{q_i}+p_i^{q_i-1}*(p_i-1)*{q_i}=p_i^{q_i-1}*(p_i+q_i*(p_i-1))$

参考链接：

https://blog.csdn.net/xiongshuxian2019/article/details/109631325

https://blog.csdn.net/consciousman/article/details/77888386

https://www.cnblogs.com/letlifestop/p/10262791.html

代码¶

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll ksm(ll a, ll b)
{
    ll ans1 = 1, ans2 = a;
    while (b != 0)
    {
        if (b & 1)
            ans1 = (ans1 * ans2) % mod;
        ans2 = (ans2 * ans2) % mod;
        b /= 2;
    }
    return ans1;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ll n, p, q, ans = 1;
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld", &p, &q);
            ans = (ans * ksm(p, q - 1) % mod * ((p + q * (p - 1)) % mod + mod) % mod) % mod;
        }
        printf("%lld\n", ans % mod);
    }
    return 0;
}

题目2¶

题目链接¶

问题 D: Master of Random

题目描述¶

Hakase provides Nano with a problem. There is a rooted tree with values on nodes. For each query,you are asked to calculate the sum of the values in the subtree. However, Nano is a rookie so she decides to guess the answer. She has known how the data generator works: it identifi es the nodes with labels from 0 to n-1 and then visits them one by one. For each i (1≤i≤n), the generator selects a node whose label is smaller than i to be its father. The pseudocode is like this:

for i = 1 to n - 1:

father[i] = random(0, i - 1);

where random(a, b) randomly generates a uniformly distributed random integer in range [a, b]. Knowing n and the value of the i-th node ai , Nano decides to randomly choose a subtree and sum up all of the values in the subtree as the answer. Now Hakase wants to know what the expectation of the answer is. Can you help her?

输入¶

The first line contains an integer T (1≤T≤10) representing the number of test cases.

For each test case, the fi rst line contains an integer n (1≤n≤100000), the number of the nodes in the rooted tree.

The second line contains n integers a0,a1,..., $a_{n-1}$ (1≤ai≤100000) represent the values of nodes.

输出¶

It can be proven that the answer equals to an irreducible fraction p/q. For each test case, print $p*q^{-1}$ mod 998244353 in one line. $q^{-1}$ is the inverse of q under module number 998244353.

样例输入¶

样例输出¶

499122178
166374063

提示¶

The shape of the tree in the first test case is unique. The father of node 1 is 0. It is possible to choose node 0 or 1 with equal possibility. The sum of the subtree with 0 as the root is 2 while the sum of the subtree with 1 as the root is 1. So the expectation is (2 + 1)/2 = 3/2. The output is 3*2-1 mod 998244353 = 400122178.

There are two possible shapes in the second test case, node 1’s father destines to be 0, but node 2’s father might be node 0 or node 1. Both conditions are equally possible.

If node 2’s father is node 0, we randomly choose a node. The sum of the subtree with node 0 as the root is 6. The sum of the subtree with node 1 as the root is 2. The sum of the subtree with node 2 as the root is 3.

If node 2’s father is node 1, we randomly choose a node. The sum of the subtree with node 0 as the root is 6. The sum of the subtree with node 1 as the root is 5. The sum of the subtree with node 2 as the root is 3.

So the expectation is (6 + 2 + 3 + 6 + 5 + 3)/6 = 25/6. The output is 25* $6^{-1}$ mod 998244353 = 166374063.

题解¶

n个点可以形成树的种类为(n-1)!，然后随机选取一个点计算子树的权值，所以总共有n!种可能。

考虑每一个点对答案的贡献，即考虑每个点在所选出的子树中有多少种可能被包含。

$0: (n-1)!$

0点只有选取0这个节点时才会被选择，共有(n-1)!种形态的树，所以为(n-1)!

$1: (n-1)!+(n-1)!$

1点只有选取0和1这两个节点时才会被选择

$2:(n-1)!+(n-1)!/2+(n-1)!$

2点只有选取0点时和选取1点（2点不在0下面）和选取2点时才会被选择

...

$k:(n-1)!+(n-1)!/2+(n-1)!/3+....+(n-1)!/k+(n-1)!$

对于每一个点，假设k出现的种树为 $cnt[k]=(n-1)!+(n-1)!/2+(n-1)!/3+....+(n-1)!/k+(n-1)!$ ，权值为a[k]，则对答案的贡献为 $cnt[k]*a[k]*(n!)^{-1}$

参考链接：

https://blog.csdn.net/weixin_44178736/article/details/113450079

代码¶

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll jc[100500] = {0};
ll a[100500] = {0};
ll ksm(ll a, ll b)
{
    ll ans1 = 1, ans2 = a;
    while (b != 0)
    {
        if (b & 1)
            ans1 = (ans1 * ans2) % mod;
        ans2 = (ans2 * ans2) % mod;
        b /= 2;
    }
    return ans1;
}
int main()
{
    jc[0] = 1;
    for (int i = 1; i <= 100000; i++)
        jc[i] = jc[i - 1] * i % mod;
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%lld", &a[i]);
        ll cnt = jc[n - 1] % mod, ans = 0;
        for (int i = 0; i < n; i++)
        {
            cnt = (cnt + jc[n - 1] * ksm(i, mod - 2) % mod) % mod;
            ans = (ans + a[i] * cnt) % mod;
        }
        ans = ans * ksm(jc[n], mod - 2);
        printf("%lld\n", ans % mod);
    }
    return 0;
}