2022“杭电杯”中国大学生算法设计超级联赛（9）签到题4题

Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Arithmetic Subsequence 18.04% (221/1225)
1002 Conquest of Masters Tour 7.07% (7/99)
1003 Fast Bubble Sort 30.05% (317/1055)
1004 If You Can’t Beat Them, Join Them! 18.50% (32/173)
1005 Leapfrogger 26.32% (5/19)
1006 Mario Party 14.61% (70/479)
1007 Matryoshka Doll 48.43% (323/667)
1008 Shortest Path in GCD Graph 12.01% (484/4029)
1009 Simple Math 4 18.75% (21/112)
1010 Sum Plus Product 77.63% (899/1158)
1011 The Alchemist of the Discrete Mathematics 5.63% (4/71)

10.Sum Plus Product

Sum Plus Product
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 35 Accepted Submission(s): 28

Problem Description
triplea has a box with n(n≥1) balls inside, where on each of the balls there is an integer written. When there are at least two balls inside the box, triplea will do the following operation repeatedly:

1. Take two balls from the box, uniformly and independently at random.
2. Supposes the numbers written on the two balls are a and b, respectively, then triplea will put a new ball in the box on which a number S+P is written, where S=a+b is the sum of a and b, and P=ab is the product of a and b.

The operation will end when there is only one ball in the box. triplea wonders, what is the expected value of the number written on the last ball? He gets the answer immediately, and leaves this as an exercise for the reader, namely, you.

Input
The first line of input consists of an integer T(1≤T≤20), denoting the number of test cases.

For each test case, the first line of input consists of an integer n(1≤n≤500), denoting the initial number of balls inside the box.

The next line contains n integers a1,a2,…,an(0≤ai<998244353), denoting the number written on each ball in the box, initially.

Output
For each test case, output an integer in one line, denoting the expected value of the number written on the last ball. Under the input constraints of this problem, it can be shown that the answer can be written as PQ, where P and Q are coprime integers and Q≢0(mod998244353). You need to output P⋅Q−1(mod998244353) as an answer, where Q−1 is the modular inverse of Q with respect to 998244353.

Sample Input
2
2
2 2
10
1 2 4 8 16 32 64 128 256 512

Sample Output
8
579063023

Source
2022“杭电杯”中国大学生算法设计超级联赛（9）

题意：

• 𝑛个数𝑎1, 𝑎2, . . . , 𝑎𝑛。每次随机选两个数𝑎, 𝑏合并成为𝑎𝑏 + 𝑎 + 𝑏，直到剩下一个数为止。
  求剩下数字的期望。答案对998244353取模。
• 20组数据,1 ≤ 𝑛 ≤ 500, 0 ≤ 𝑎𝑖 < 998244353

思路：

• 直接两两合并即可。

#include
using namespace std;
typedef long long LL;
const LL maxn = 510, mod = 998244353;

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        LL x, y;  cin>>x;
        for(int i = 2; i <= n; i++){
            cin>>y;  x = (x+y+x*y%mod)%mod;
        }
        cout<<x<<"\n";
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8.Shortest Path in GCD Graph

Shortest Path in GCD Graph
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 619 Accepted Submission(s): 167

Problem Description
There is an edge-weighted complete graph Kn with n vertices, where vertices are labeled through 1,2,…,n.
For each 1≤i

You need to answer q queries. In each query, given two vertices u,v, you need to answer the length of the shortest path as well as the number of shortest paths between u,v. Since the number of shortest paths may be too large, you only need to output it modulo 998244353.

Input
The first line contains two integers n,q(2≤n≤107,1≤q≤50000), denoting the number vertices in the graph and the number of queries, respectively.

Then q lines follow, where each line contains two integers u,v(1≤u,v≤n,u≠v), denoting a query between u and v.

Output
For each query, output one line contains two integers, denote the length and number of shortest path between given nodes, respectively. Note that only the number of shortest paths should be taken modulo 998244353.

Sample Input
6 2
4 5
3 6

Sample Output
1 1
2 2

Source
2022“杭电杯”中国大学生算法设计超级联赛（9）

题意：

• 给定𝑛个点的完全图，两个点之间距离为它们的gcd，𝑞次询问两个点之间的最短路以及方案数。
• 𝑛 ≤ 10^7, 𝑞 ≤ 50000.

思路：

• 首先最短路长度不超过2，因为对任意(𝑥,𝑦)，沿路径𝑥 → 1 → 𝑦即可得到一条长度为2的路径。最短路长度为1当且仅当𝑔𝑐𝑑 (𝑥,𝑦) = 1。
• 否则等价于询问[1, 𝑛]中满足𝑔𝑐𝑑 (𝑥, 𝑧) =1且𝑔𝑐𝑑 (𝑦, 𝑧) = 1的𝑧的数量，分解𝑥,𝑦后用容斥可以解决。（容斥原题参考 AcWing890能被整除的数， 求 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个）
• 注意𝑔𝑐𝑑 (𝑥,𝑦) = 2时，直接𝑥 →𝑦也是一 条长度为2的路径。需要特判是否+1。
• 单组数据时间复杂度: 𝑂(𝑛 + 𝑄 · 2^𝑝 )，其中𝑝 ≤ 12为𝑥,𝑦的不同质因子个数。

//1008
#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const int maxn = 1e7+10;
LL gcd(LL a, LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a, LL b){ return a/gcd(a,b)*b; }

int readint(){
    int x=0, op=1;  char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch=='-')op=-1; ch = getchar(); }
    while(ch >= '0' && ch <= '9'){ x=x*10+ch-'0'; ch = getchar(); }
    return x*op;
}
void write(int x){
	if(x<0){x=-x;putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

//线性筛预处理优化试除法，哈希维护每个数的质因数
int vis[maxn], primes[maxn], cnt;
void get_primes(int n){
    vis[0]=vis[1]=1;
    for(int i = 2; i < n; i++){
        if(!vis[i])primes[++cnt]=i;
        for(int j = 1; primes[j] <= n/i; j++){
            vis[primes[j]*i] = 1;
            if(i%primes[j]==0)break;
        }
    }
}
const int maxx = 1e6+10;
int mp[maxx][10], len[maxx];
unordered_map<int,int>has; int tot=0;
void get_zys(int x){
    int t = has[x];
    for(int i = 1; i <= cnt && x >= primes[i]; i++){
        if(x%primes[i]==0){
            while(x%primes[i]==0)x /= primes[i];
            mp[t][len[t]++] = primes[i];
        }
    }
    if(x > 1)mp[t][len[t]++] = x;
}


int n, q;

//acwing 890, ans = 1-n中能被p[1~m]至少一个数整除的数
int p[50], m, ans;
void dfs(int cur, LL sum, int opt){
	if(sum > n)return ;
	if(cur)ans += n/sum*opt;
	opt = -opt;
	for(int i=cur+1; i <= m; i++){
		dfs(i,sum*p[i],opt);
	}
}
int calc(){
    ans = 0;
    dfs(0,1,-1);
    return n-ans;
}

int main(){
    n = readint();
    q = readint();
    get_primes(sqrt(n)+1);
    while(q--){
        int u, v;  
        u = readint();
        v = readint();
        if(gcd(u,v)==1){ write(1); putchar(' ');
            write(1); putchar('\n'); continue; 
        }
        int ok = 0;
        if(gcd(u,v)==2){
            ok = 1;
        }

        int cnt = 0;
        if(!has.count(u))has[u] = tot++;
        if(!has.count(v))has[v] = tot++;
        if(len[has[u]]==0)get_zys(u);
        if(len[has[v]]==0)get_zys(v);
        m = 0;
        u = has[u];  v = has[v];

        //合并u的质因数和v的质因数, 去重后存到数组p中
        for(int i = 0, j = 0; i<len[u] || j < len[v]; ){
            if(mp[u][i]==mp[v][j]){
                p[++m] = mp[u][i];
                i++; j++;
            }else if(i!=len[u] && (mp[u][i]<mp[v][j] || j==len[v])){
                p[++m] = mp[u][i];
                i++;
            }else{
                p[++m] = mp[v][j];
                j++;
            }
        }

        write(2); putchar(' ');
        write(calc()+ok); putchar('\n');
    }
    return 0;
}


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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

//1008, 精简版(去掉了哈希, 快读，手写合并, 优化了容斥)
#include
using namespace std;
typedef long long LL;
const int maxn = 1e7+10;
LL gcd(LL a, LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a, LL b){ return a/gcd(a,b)*b; }

//线性筛预处理优化试除法，vector存储每个数的质因数
int vis[maxn], primes[maxn], cnt;
void get_primes(int n){
    vis[0]=vis[1]=1;
    for(int i = 2; i < n; i++){
        if(!vis[i])primes[++cnt]=i;
        for(int j = 1; primes[j] <= n/i; j++){
            vis[primes[j]*i] = 1;
            if(i%primes[j]==0)break;
        }
    }
}
vector<int>mp[maxn];
void get_zys(int x){
    int t = x;
    for(int i = 1; i <= cnt && x >= primes[i]; i++){
        if(x%primes[i]==0){
            while(x%primes[i]==0)x /= primes[i];
            mp[t].push_back(primes[i]);
        }
    }
    if(x > 1)mp[t].push_back(x);
}

int n, q;

//acwing 890, ans = 1-n中能被p[1~m]至少一个数整除的数
int p[50], m, ans;
void dfs(int cur, LL sum, int opt){
	if(sum > n)return ;
	if(cur)ans += n/sum*opt;
	opt = -opt;
	for(int i=cur+1; i <= m; i++){
		dfs(i,sum*p[i],opt);
	}
}
int calc(){
    ans = 0;
    dfs(0,1,-1);
    return n-ans;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    cin>>n>>q;
    get_primes(sqrt(n)+1);
    while(q--){
        int u, v;  cin>>u>>v;
        if(gcd(u,v)==1){ cout<<"1 1\n";  continue; }
        int ok = 0;
        if(gcd(u,v)==2)ok = 1;
        int cnt = 0;
        if(mp[u].size()==0)get_zys(u);
        if(mp[v].size()==0)get_zys(v);
        unordered_set<int>se(mp[u].begin(),mp[u].end());
        se.insert(mp[v].begin(),mp[v].end());
        m = 0;
        for(auto x : se)p[++m] = x;
        cout<<2<<' '<<calc()+ok<<"\n";
    }
    return 0;
}


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
65
66
67
68
69
70
71
72

7.Matryoshka Doll

Matryoshka Doll
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 207 Accepted Submission(s): 117

Problem Description
zyb bought n matryoshka dolls during his visit to Moscow, with sizes a1,a2,…,an, respectively, sorting from smallest to largest.

A matryoshka of size i can be put into another matryoshka of size j if and only if j−i≥r, where r is some given integer parameter.

zyb wishes to divide all n matryoshka dolls into k groups, such that one can form a nested matryoshka doll in each group, where a group of matryoshka dolls with indices c1,c2,…,cm (1≤c1nested matryoshka doll iff ∀1≤i

zyb wants to know how many ways there are to divide the n dolls into k groups satisfying the requirement above. Note that divisions such as {{1,2},{3,4}} and {{3,4},{1,2}} are considered the same way. As the answer may be too large, you only need to output the answer modulo 998244353.

Input
The first line contains an integer T(1≤T≤20), denoting the number of test cases.

For each test case, the first line contains three integers n,k,r(1≤k≤n≤5000,1≤r≤109), denoting the number of matryoshka dolls, the number of groups zyb wants to divide into, and the parameter, respectively.

The next line contains n integers a1,a2,…,an(1≤a1≤a2≤…≤an≤109), denoting the sizes of the matryoshka dolls.

It is guaranteed that ∑n≤50000 over all test cases.

Output
For each test case, output an integer in a line, denoting the answer taken modulo 998244353.

Sample Input
2
4 3 2
1 2 3 4
4 2 1
1 1 2 2

Sample Output
3
2

Source
2022“杭电杯”中国大学生算法设计超级联赛（9）

题意：

• 有𝑛个套娃，大小为𝑎1 ≤ 𝑎2 ≤ … ≤ 𝑎𝑛，现在要将这些套娃分成𝑘组，每组套娃按照大小排序后相邻两个套娃之间的大小差距要求≥ 𝑟，求方案数。
• 20组数据,1 ≤ 𝑘 ≤ 𝑛 ≤ 5000, 1 ≤ 𝑎𝑖 , 𝑟 ≤ 10^9，输入保证所有数据中sum(𝑛) ≤ 50000

思路：

• 𝑑𝑝(𝑥,𝑦)表示将前𝑥个套娃分成𝑦组的方案数。
  转移时考虑第x个套娃放在前面的某一组（x-1,y），或者单独一组(x-1,y-1)。
  即𝑑𝑝(𝑥,𝑦) = 𝑑𝑝(𝑥 − 1,𝑦 − 1) + 𝑑𝑝(𝑥 − 1,𝑦) · max{0,𝑦 − 𝑓 (𝑥)}， 𝑓(𝑥)表示满足1 ≤ 𝑧 < 𝑥且𝑎𝑥 − 𝑟 < 𝑎𝑧 ≤ 𝑎𝑥的𝑧的个数, 即y组中不能放入x进行转移的组的数量。
• 只要知道有几个组可以转移就行了，不需要知道前面哪些组可以转移，也不需要维护前面每一组的信息，只要知道能转移的组的个数就行，不能转移的个数可以维护前面最后一个a[p]+r<=a[i]的数的位置p得到。
  分成y组不需要知道每组的最大值，因为反正dp是考虑了所有情况的，肯定会包含那些不能进行转移的情况，只需要y把这些情况减掉就行了。
• 单组数据复杂度O(n^2)

//1007
#include
typedef long long LL;
using namespace std;
const int maxn = 5050, mod = 998244353;
int a[maxn], dp[maxn][maxn];                    //前i个数分成j组的方案数
int main(){
    int T;  cin>>T;
    while(T--){
        memset(dp,0,sizeof(dp));
        int n, k, r;  cin>>n>>k>>r;
        for(int i = 1; i <= n; i++)cin>>a[i];
        int p = 0;  dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            while(p+1<i && a[p+1]+r<=a[i])p++;  //p维护前面最后一个a[p]+r<=a[i]的数的位置
            int s = i-p-1;                      //前面的不能转移的数的个数
            for(int j = s+1; j <= i; j++){      //单独成组，或放在前面的某一组
                dp[i][j] = (dp[i-1][j-1]+1ll*dp[i-1][j]*(j-s))%mod;
            }
        }
        cout<<dp[n][k]<<"\n";
    }
    return 0;
}


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

3.Fast Bubble Sort

Fast Bubble Sort
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 129 Accepted Submission(s): 61

Problem Description
Given an array A=(a1,a2,…,am) of length m, denote by array B(A) the output of a single iteration of bubble sort with input array A, i.e., the output of the following algorithm with input array A.

You may perform the following operation any number (including zero) of times on the array A=(a1,a2,…,am):

1. Select an interval [i,j] where 1≤i≤j≤m, and cyclically shift all elements of ai,ai+1,…,aj−1,aj in either direction, so that they become aj,ai,ai+1,…,aj−1 or ai+1,…,aj−1,aj,ai.

For example, if we cyclically shift the interval [1,4] of the array A=[1,2,3,4,5] to the right, the resulting array would be A′=[4,1,2,3,5].

You are now given a permutation P=(p1,p2,…,pn) of length n and you need to answer q independent queries of the following form:

1. In the i-th query, you are given parameters 1≤li≤ri≤n and you are supposed to find the minimum number of above operations needed to transform the subarray P[li,ri] to B(P[li,ri]), where P[li,ri]=(pli,pli+1,…,pri).

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

For each test case, the first line contains two integers n,q (1≤n,q≤105), denoting the length of permutation P and the number of queries, respectively.

The second line contains n distinct integers p1,p2,…,pn (1≤pi≤n).

Each of the following q lines contains two integers li,ri (1≤li≤ri≤n), denoting the parameters for the i-th query.

Output
For each query of each test case, output an integer in one line, denoting the answer.

Sample Input
1
10 5
3 7 9 2 6 4 5 8 10 1
1 10
2 6
7 9
4 9
3 3

Sample Output
2
1
0
1
0

Source
2022“杭电杯”中国大学生算法设计超级联赛（9）

题意：

• 给定一个长度为𝑁的数组𝐴 = (𝑎1, 𝑎2, . . . , 𝑎𝑛), 令𝐵(𝐴)表示对𝐴进行一次bubble sort循环之后得到的数组。令𝑛𝑢𝑚(𝐴)表示从𝐴到𝐵(𝐴)最少需要移动元素(数组区间循环移位)的次数。
• 给定一个1 − 𝑛的排列𝑃， 以及𝑞 组 1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛，求𝑛𝑢𝑚(𝑃 [𝑙, 𝑟 ])。
• 10组数据,1 ≤ 𝑛, 𝑞 ≤ 10^5。

思路：

• 假设𝑃 = 𝑛1𝜆1𝑛2𝜆2 · · · 𝑛𝑘𝜆𝑘 ,则 𝐵(𝑃) = 𝜆1𝑛1𝜆2𝑛2 · · · 𝜆𝑘𝑛𝑘 ,其中𝑛1, · · · , 𝑛𝑘为从左到右的局部最大值且有𝑛1 < 𝑛2 < · · · < 𝑛𝑘。则不难证明答案为非空𝜆𝑖的个数。
  即相当于对于给定区间，一次冒泡排序需要将所有逆序a[i]>a[i+1]的a[i]都移动到后面第一个大于它的数前方，答案为满足递增的局部最大值中间的数的个数。
• 将询问离线, 每次从𝑛到1倒序扫描左端点𝑙并回答所有左端点为𝑙的询问。
  对于每个固定的左端点𝑙，[𝑙, 𝑛]中从左到右的局部最大值可以通过单调栈维护，局部最大值插入/删除对于答案的影响可以用树状数组/线段树快速更新/求解。
• 单组数据时间复杂度为𝑂( (𝑛 + 𝑞) log 𝑛)

//1003
#include
using namespace std;
typedef pair<int, int> PII;
const int maxn = 1e5+10, mod = 998244353;

int n, q, p[maxn];
vector<PII>info[maxn];
int now[maxn], ans[maxn];

//树状数组
int b[maxn];
void add(int x, int v){ for(int i = x; i <= n; i+=i&(-i))b[i]+=v;}
int query(int x){ int ans=0;for(int i=x;i>0;i-=i&(-i))ans+=b[i];return ans;}

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        cin>>n>>q;
        for(int i = 0; i < maxn; i++)info[i].clear();
        for(int i = 0; i <= n+5; i++)b[i]=0, now[i]=0;
        for(int i = 0; i < n; i++)cin>>p[i];  p[n] = n+1;
        for(int i = 0; i < q; i++){
            int l, r;  cin>>l>>r;  l--;  r--;
            info[l].push_back({i,r});
        }
        //树状数组更新答案，先给[u,u+1]都+1,最后再/2。
        //若第一个大于pi的数在r的外面，可以少移1次（最后不用交换）
        auto update=[&](int u){
            add(u+1,(now[u+1]?-1:1)), now[u+1]^=1;
            add(u+2,(now[u+2]?-1:1)), now[u+2]^=1;
        };
        //单调递减栈，维护[l,n]局部最大值的位置
        stack<int>st;  st.push(n);
        //离线询问，对于每个固定的左端点l进行处理
        for(int i = n-1; i >= 0; i--){
            //不断出栈直到找到第一个比p[i]大的值的位置
            while(st.size() && p[i]>p[st.top()]){
                //中间遇到的每个值的位置都+1（操作次数+1）
                update(st.top());  st.pop();
            }
            st.push(i); update(i);
            for(auto x : info[i]){
                int id = x.first, r = x.second;
                if(i==r)ans[id] = 0;
                else ans[id] = (query(r+1)-query(i))/2;
            }
        }
        for(int i = 0; i < q; i++)cout<<ans[i]<<'\n';
    }
    return 0;
}



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