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

#include 
using namespace std;
typedef long long ll;
typedef long double ld;
const int mod = 998244353,N = 1000;
ll a[N];

int main(){
	int t,n;
	scanf("%d",&t);
	while(t--){
	    scanf("%d",&n);
	    for(int i=1;i<=n;i++) {
	    	scanf("%d",&a[i]);
		}
		ll x=a[1];
		for(int i=2;i<=n;i++){
			x=((x+a[i])%mod+x*a[i]%mod)%mod;
		}
		printf("%lld\n",x);
	}
	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

#include 
#include 
using namespace std;
int dp[1001][1001];
int main()
{
	int n, m;
	cin >> n >> m;
	dp[0][0] = 1;			//把0个人分为0份方案为1
	dp[0][1] = 0;			//把0个人分为1份方案为0
	for(int i=1;i<=n;i++)
		for (int j = 1;j <= m;j++)
		{
			dp[i][j] = dp[i - 1][j - 1];			//有1的情况
			if (i >= j)
			{
				dp[i][j] += dp[i - j][j];		//无1的情况
			}
		}
	cout << dp[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include 
using namespace std;
typedef long long ll;
const int N = 5010,mod = 998244353;
int n,k;
ll r,a[N],dp[N][N];


int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%lld",&n,&k,&r);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=1;i<=n;i++){
			ll x=0;
			for(int j=1;j

• 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

1008.Shortest Path in GCD Graph

题意：
给出一个n个点的带权图，从i到j的边权为gcd(i,j)。
给出q次询问，每次询问输出点u和点v之间的最短距离以及路径条数。

思路：
最短路的长度一定<=2。
当gcd(u,v)==1时，最短路长度为1且只有一条；
否则，最短路长度为2，当gcd(u,v)==2时，
ans+=1;ans+= gcd(u,p)==1&&gcd(p,v)==1的点p的数量，
分解u，v后用容斥可以计算。

代码：

#include 
using namespace std;
typedef long long ll;
const int N = 1e7+10,mod= 998244353;
int prime[N/10],f[N],n,m,q,res;//f[i]表示i的最小质因子 
set st;
vector a;
bool p[N];

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

void Prime(int n){
    int cnt=0;
    for(int i=2;i<=n;i++){
        //p数组标记这个数是否为质数 
        //如果i就是质数，那么最小质因子就是它本身 
        if(!p[i]) prime[++cnt]=i,f[i]=i;//prime数组记录所有质数 
        
        for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
            p[prime[j]*i]=1;
            f[prime[j]*i]=prime[j];//最小质因子是prime[j] 
            if(i%prime[j]==0) break; 
        }
    }
}

void div(int x){
    while(x>1){
        int y=f[x];//获取x的最小质因子
        if(!st.count(y)) st.insert(y);
        while(x%y==0) x/=y;//除尽这个质因子 
    }
}

void dfs(int x,int y,int z){
    if(x==m){
        res+=z*(n/y)%mod;
        return;
    }
    dfs(x+1,y,z);
    if(y<=n/a[x]) dfs(x+1,y*a[x],-z);//容斥 
}

int work(int x,int y){
    st.clear();
    a.clear();
    div(x),div(y);
    for(auto it:st) a.push_back(it);//将set里面的所有元素放进vector数组中
    m=a.size();
    res=0;
    dfs(0,1,1);
    return res; 
}

int main(){
    scanf("%d%d",&n,&q);
    Prime(n);
    while(q--){
        int u,v;
        scanf("%d%d",&u,&v);
        if(gcd(u,v)==1){
            puts("1 1");
        }
        else{
            int ans=work(u,v);
            if(gcd(u,v)==2) ans++;
            ans%mod;
            printf("2 %d\n",ans);
        }
    }
    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