2021 ICPC济南站的签到题：C & K

题目在PTA的教育超市里可以找到：https://pintia.cn/market/item/1459833348620926976

C题：博弈+组合数学
这题给的样例有很好的提示作用。可以想到如果最大的数有偶数个，那么就得成对拿走，如果是有奇数个，那么当前有机会拿的人一定会拿。从小数往大数遍历，可以发现大数可以随意穿插在小数序列之间，不受除了位置数量以外的特殊限制。

因为要成对，设当前数的个数为n，如果n是偶数，则可以放的位置有，suf+n/2个，所以是suf+n/2取n/2个位置。suf是更小数的总个数。放完之后相同数可以随意排列，再乘上阶乘即可。
如果n是奇数，则当前数必须第一个被轮到的选手拿一次，然后变成偶数的情况，显然这样的变动并不会多做贡献。

#include 
using namespace std;

const int N = 1e6 + 5;
const long long MOD = 998244353;

int n, a[N], num[N], mul[N], tot;

long long ksm(long long a, long long b) {
	long long res = 1;
	while (b) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

long long inv(long long x) {
	return ksm(x, MOD - 2);
}

long long cal(long long a, long long b) {
	long long res = 1;
	for (long long i = 1; i <= a; i++) {
		res = res * (b - i + 1) % MOD;
		res = res * inv(i) % MOD;
	}
	return res;
}

int main(void) {
	mul[0] = 1;
	for (long long i = 1; i < N; i++) {
		mul[i] = mul[i - 1] * i % MOD;
	}
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n);
	int pos = 1;
	while (pos <= n) {
		int cnt = 1;
		while (pos <= n && a[pos] == a[pos + 1]) {
			pos++; cnt++;
		}
		num[++tot] = cnt;
		pos++;
	}
	long long ans = 1, sum = 0; 
	for (int i = 1; i <= tot; i++) {
		long long n = num[i];
		sum += n / 2;
		ans = ans * cal(n / 2, sum) % MOD * mul[n] % MOD;
		sum += n / 2;
		if (n & 1) sum++;
	}
	printf("%lldn", ans);
	return 0;
}

K题：欧拉遍历，即不走到底部不会半途返回的遍历。
这一题主要是找规律试出来，简单的画几个样例，发现无论先走哪课子树，结果都不变。

#include 
using namespace std;

const int N = 105;

int t, n;
vector e[N];
long long ans, step;

void dfs(int u, int f) {
	for (int i = 0; i < e[u].size(); i++) {
		int v = e[u][i];
		if (v == f) continue;
		step++;
		ans += step;
		dfs(v, u);
		step++;
	}
}

int main(void) {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) e[i].clear();
		for (int i = 1; i < n; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		ans = step = 0;
		dfs(1, -1);
		printf("%.99fn", 1.0 * ans / (n - 1));
	}
	return 0;
}