https://ac.nowcoder.com/acm/contest/2927

B. 数字游戏

 

题意：有2n-1个数：2,3,4…2n。 裁判会随机擦掉一个数字。 然后有两个非常聪明的同学甲和乙玩游戏，他们都会采取最优策略。首先乙擦掉一个，甲擦掉一个，再乙擦，再甲擦…直到黑板上只剩下两个数。 如果这两个数互质，那么甲胜，否则乙胜。 问裁判有多少种擦数的方案，使得乙必胜。 2≤n≤10182\leq n\leq 10^{18}

如果擦去奇数，则剩下的偶数比奇数多2个，最终一定可以剩下2个偶数，则乙必胜。

如果擦去偶数，例如6，则一定可以(2,3),(4,5),(7,8),(9,10)这样奇偶搭配，相邻差1，则一定互质，只要甲每次删乙删的数的对应数，一定可以剩下一对，则甲必胜。

那么就是问奇数个数即n-1.

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll n;
int main() {
    cin >> n;
    cout << n - 1 << endl;
    return 0;
}

 

C. 最大生成树

 

题意：有一个n个点的无向完全图，边(i,j)的边权为 ∣i−j∣|i-j|，求最大生成树边权和。2≤n≤10182\leq n\leq 10^{18}

首先连接(1,n)，其它点选择1和n中距离远的那个连上。

本题保证n是偶数，但是模完就不一定了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll two = (mod + 1) / 2;;
ll n;
int main() {
	cin >> n;
	n %= mod;
	ll ans = n - 1;
	ans = (ans + (n - 2) * (2 * n - 2 - n* two % mod) % mod*two%mod) % mod;
	ans = (ans + mod) % mod;
	cout << ans << endl;
	return 0;
}

 

E. 树

 

题意：一棵树，求 ∑i=1n∑j=1ndis2(i,j)\sum_{i=1}^n\sum_{j=1}^n dis^2(i,j)。

树上dp

求dis和的话很简单，但是这里要平方和。

但是仍然可以考虑树上dp，把平方和拆开来，继续考虑父子关系。

dp[v]=dp[u]+2* (v的子树外的点到u的dis和-v的子树内点到u的dis和)+n​，u为v的父亲。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n;
vector<int>G[N];
ll dis[N], dp1[N], sum, dp2[N], ans[N];
int sz[N];
void dfs1(int u, int _fa, int d) {
	sz[u] = 1; dis[u] = d;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs1(v, u, d + 1);
		sz[u] += sz[v];
	}
}
void dfs2(int u, int _fa) {
	for (int v : G[u]) {
		if (v == _fa)continue;
		dp1[v] = (dp1[u] + n - 2 * sz[v] + mod) % mod;
		dfs2(v, u);
		dp2[u] = (dp2[u] + dp2[v] + sz[v]) % mod;
	}
}
void dfs3(int u, int _fa) {
	for (int v : G[u]) {
		if (v == _fa)continue;
		ans[v] = (ans[u] + 2 * ((dp1[v] - dp2[v] - (n - sz[v]) - (dp2[v] + sz[v]) + 3 * mod) % mod) % mod + n) % mod;
		dfs3(v, u);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0, 0);
	for (int i = 1; i <= n; i++) {
		ans[1] = (ans[1] + dis[i] * dis[i] % mod) % mod;
		dp1[1] = (dp1[1] + dis[i]) % mod;
	}
	dfs2(1, 0);
	dfs3(1, 0);
	for (int i = 1; i <= n; i++)sum = (sum + ans[i]) % mod;
	cout << sum << endl;
	return 0;
}