2022杭电多校9(总结+补题)

总结

坐牢局，开局十分钟签了1010之后看的每个题都觉得不可做，两个队友讨论了三个小时做出了1003之后队友1提出了1008的思路，我俩各写了十几发都t了，赛后发现是容斥写假了，T__T！！！

题解

1010 - Sum Plus Product

题意：

盒子里有 $n$ 个球，每次随机取出两个球 $a,b$ ，放回一个球 $(a+b)+(ab)$，问最后一个球的期望值是多少

做法：

取球的顺序与最后的结果无关（嗯取就完事了）

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
const int mod = 998244353;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        int ans=0;
        cin>>ans;
        for(int i=1;i<n;i++)
        {
            int x;
            cin>>x;
            ans=((ans+x)+ans*x)%mod;
        }
        cout<<ans<<endl;
    }   
    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

1008 - Shortest Path in GCD Graph

题意：

给你一张 n 个点的图，两点之间的边权为 $gcd(i,j)$ ，有 $q$ 个询问，每次询问给你两个点 $u,v$ 你需要回答 $u,v$ 之间最短路及最短路的路径数量。

做法：

我们知道，如果 $u,v$ 两点中 $gcd(u,v)=1$ 那这两点的最短路为 $1$ ，路径数量也为 $1$，当 $gcd(u,v)\ne 1$ 时，我们至少可以走 $u-1-v$ 这条路使两点的最短路为 $2$ ，因此我们可以将这个问题转化为找 $k$ 的个数使得 $k$ 满足 $gcd(k,u)=gcd(v,k)=1$ ，其实也就是找 $1-n$ ,中与 $lcm(u,v)$ 互质的数的个数，我们可以使用容斥来做。

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
inline int gcd(int a,int b){return b ? gcd(b , a % b) : a ;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    while(k--)
    {
        int u,v;
        cin>>u>>v;
        int gc=gcd(u,v);
        int ans=0;
        if(gc==1)
        {
            cout<<1<<" "<<1<<endl;
            continue;
        }
        else if(gc==2)
            ans=1;
        vector<int> p;
        unordered_map<int,int> mp;
        for(int i=2;i*i<=u;i++)
        {
            if(u%i==0)
            {
                if(!mp[i])
                {
                    p.emplace_back(i);
                    mp[i]=1;
                }
                while(u%i==0)
                    u/=i;
            }
        }
        if(u>1&&!mp[u])
        {
            p.emplace_back(u);
            mp[u]=1;
        }
        for(int i=2;i*i<=v;i++)
        {
            if(v%i==0)
            {
                if(!mp[i])
                {
                    p.emplace_back(i);
                    mp[i]=1;
                }
                while(v%i==0)
                    v/=i;
            }
        }
        if(v>1&&!mp[v])
        {
            p.emplace_back(v);
            mp[v]=1;
        }
        int sz=p.size();
        int sum=0;
        function<void(int,int,int)> dfs = [&](int now,int res,int nb)
        {
            if(res==0)
            {
                if(nb>0)
                {
                    if(nb&1)
                        sum+=n/now;
                    else
                        sum-=n/now;
                }
                return;
            }
            for(int i=0;i<2;i++)
            {
                if(i==1)
                {
                    int n1=now*p[sz-res];
                    if(n1<=n)
                        dfs(n1,res-1,nb+1);
                }
                else
                    dfs(now,res-1,nb);
            }
        };
        dfs(1,sz,0);
        cout<<2<<" "<<ans+n-sum<<endl;
    }
    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