2020杭电多校（第五场）

比赛链接

收获

• 一些看似复杂的找规律题直接找一个恰当的数据结构模拟就好。

---

1001 Tetrahedron

用等体积法求出 $h$ 和 $a,b,c$ 的关系（底面积用余弦定理+正弦定理）为：

$$h=\frac{abc}{\sqrt{a^2b^2+b^2c^2+c^2a^2}}$$

于是要求的是：

$$\frac{1}{h^2}=\frac{a^2b^2+b^2c^2+c^2a^2}{a^2b^2c^2}=\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}$$

期望显然是：

$$E\left(\frac{1}{h^2}\right)=3\cdot\frac{\sum\limits_{k=1}^n\frac{1}{k^2}}{n}$$

预处理一下，回答即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 6000005;
const LL MOD = 998244353;

int T, n;
LL sum[N];

LL fpow(LL bs, LL idx){
	bs %= MOD;
	LL res = 1;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

int main(){
	for(int i = 1; i <= 6000000; i++)
		sum[i] = (fpow(1ll * i * i, MOD-2) + sum[i-1]) % MOD;
	for(read(T); T; T--){
		read(n);
		printf("%lld\n", 3ll * sum[n] % MOD * fpow(n, MOD-2) % MOD);
	}
	return 0;
}

---

1003 Boring Game

折叠 $k$ 次后展开，形成 $2^k$ 个格子，每一个格子建立一个链表。每一次折叠，就是把当前最左端的链表反转之后接到最右端的链表尾部、次左端的链表反转后接到次右端的链表尾部、……如此便得到下一阶段的链表。反复执行直到只剩下一个链表，按 $p$ 编号即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 2005;

int T, n, k;
int val_col[N*405], ans[405][N], p[N*405];

struct List{
	int nxt, col;
	List(){ nxt = col = 0; }
}a[N];
int head[N], tail[N];
void reverseList(int x){
	int pre = 0, now = head[x];
	while(now){
		int nxt = a[now].nxt;
		a[now].nxt = pre; pre = now; now = nxt;
	}
	pre = head[x]; head[x] = tail[x]; tail[x] = pre;
}

inline void initCASES(){
	for(int i = 1; i <= (1 << k); i++){
		head[i] = tail[i] = 0;
		val_col[i] = 0;
		a[i].nxt = a[i].col = 0;
	}
}

int main(){
	for(read(T); T; T--){
		read(n, k);
		for(int i = 1; i <= 2 * n * (1 << k); i++)	read(p[i]);
		initCASES();
		for(int i = 1; i <= (1 << k); i++)
			head[i] = i, tail[i] = i, a[i].col = i;
		for(int len = (1 << k); len > 1; len >>= 1){
			for(int l = (1 << k) - len + 1, r = (1 << k); l < r; l++, r--){
				reverseList(head[l]);
				a[tail[r]].nxt = head[l];
				tail[r] = tail[l];
			}
		}
		int now = head[(1<<k)], id = 2 * n * (1 << k);
		while(now)	val_col[id] = a[now].col, id -= 2 * n, now = a[now].nxt;
// for(int id = 1; id <= 2 * n * (1 << k); id++)
// 	printf("%d: %d\n", id, val_col[id]);
		bool up = true;
		id = (1 << k) * 2 * n;
		while(id){
			int i = id;
			if(up){
				for(int j = 2 * n; j >= 1; j--)
					ans[j][val_col[i]] = p[id--];
			}
			else{
				for(int j = 1; j <= 2 * n; j++)
					ans[j][val_col[i]] = p[id--];
			}
			up ^= 1;
		}
		for(int i = 1; i <= 2 * n; i++){
			for(int j = 1; j <= (1 << k); j++){
				printf("%d", ans[i][j]);
				if(i == 2 * n && j == (1 << k))	putchar('\n');
				else	putchar(' ');
			}
		}
	}
	return 0;
}

---

1007 Tree

设 $dp[i][0/1]$ 表示以 $i$ 为根的子树内是否有 $>k$ 的点的最大权值和，注意这个权值和要加上 $i$ 到父节点的边权，则：

• $dp[i][0]$ 等于最大的 $k-1$ 的子节点 $dp[sons][0]$ 之和加上到父节点的边权；
• $dp[i][1]$ 等于所有子节点 $dp[sons][0]$ 之和加上到父节点的边权，或者 $dp[i][0]$ 把某一个子节点从 $dp[son][0]$ 换成 $dp[son][1]$.

更新答案特别注意一下，除了所有 $dp[i][0],dp[i][1]$ 取 $\max$ 之外，还有一种情形：

• 不取第 $i$ 个点向上到父节点的那条边，多取一个子节点。注意这个情形是没被 $dp$ 状态包含的。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)

const int N = 200005;

int n, k;
struct Edge{
	int nxt, to; LL d;
}edge[N<<1];
int head[N], edgeNum, deg[N];
void addEdge(int from, int to, LL d){
	edge[++edgeNum] = (Edge){head[from], to, d};
	head[from] = edgeNum;
	deg[to]++;
}

struct Node{
	LL val; int id;
	bool operator < (const Node &A) const{ return val > A.val; }
};
LL dp[N][2], ans;
void DP(int x, int f, LL df){
	dp[x][0] = dp[x][1] = df;
	vector<Node> v;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == f)	continue;
		DP(edge[i].to, x, edge[i].d);
		v.emplace_back((Node){dp[edge[i].to][0], edge[i].to});
		dp[x][1] += dp[edge[i].to][0];
	}
	int sz = v.size();
	sort(v.begin(), v.end());
	for(int i = 0; i < min(sz, k - 1); i++)	dp[x][0] += v[i].val;
	
	if(k >= 2){
		for(int i = 0; i < sz; i++){
			if(i < k - 1)	dp[x][1] = max(dp[x][1], dp[x][0] - v[i].val + dp[v[i].id][1]);
			else	dp[x][1] = max(dp[x][1], dp[x][0] - v[k-2].val + dp[v[i].id][1]);
		}
	}
	else	dp[x][1] = max(dp[x][1], df);
	
	LL res = dp[x][0] - df + (sz >= k ? v[k-1].val : 0);
	ans = max(ans, res);
	for(int i = 0; i < sz; i++){
		if(i < k)	ans = max(ans, res - v[i].val + dp[v[i].id][1]);
		else	ans = max(ans, res - v[k-1].val + dp[v[i].id][1]);
	}
}

inline void initCASES(){
	edgeNum = 0;
	ans = 0;
	for(int i = 1; i <= n; i++){
		head[i] = deg[i] = 0;
		dp[i][0] = dp[i][1] = 0;
	}
}

int main(){
	int T; for(read(T); T; T--){
		read(n, k);
		initCASES();
		for(int i = 1; i < n; i++){
			int u, v; LL d; read(u, v, d);
			addEdge(u, v, d), addEdge(v, u, d);
		}
		if(k == 0){ puts("0"); continue; }
		int rt = 0;
		for(rt = 1; rt <= n; rt++) if(deg[rt] == 1)	break;
		DP(rt, 0, 0);
		for(int i = 1; i <= n; i++)
			ans = max(ans, max(dp[i][0], dp[i][1]));
		printf("%lld\n", ans);
	}
	return 0;
}

---

1009 Paperfolding

向上或向下折 $a$ 次，就会形成 $2^a$ 条折痕，分割出 $2^a+1$ 条横带；同理，向左或向右折 $b$ 次，就会形成 $2^b$ 条折痕，分割出 $2^b+1$ 条竖带；向上向下与向左向右的顺序不重要，只要向上或向下折 $a$ 次，向左或向右折 $b$ 次，答案就是 $(2^a+1)(2^b+1)$.

于是长度为 $n$ 的串的期望答案是：

$$\frac{\sum\limits_{i=0}^n\binom{n}{i}2^i2^{n-i}(2^i+1)(2^{n-i}+1)}{4^n}$$

$i$ 是枚举向上或向下折的次数，$\binom{n}{i}$ 是从 $n$ 次操作中选 $i$ 次向上或向下折，$2^i$ 是每一次向上/向下折可以选择是向上还是向下，$2^{n-i}$ 是每一次向左/向右折可以选择是向左还是向右，$(2^i+1)(2^{n-i}+1)$ 就是这么折的答案，$4^n$ 是总折叠方案数。

化简上式：

$$\begin{align} \frac{\sum\limits_{i=0}^n\binom{n}{i}2^i2^{n-i}(2^i+1)(2^{n-i}+1)}{4^n}&=\frac{\sum\limits_{i=0}^n\binom{n}{i}(2^n+2^i+2^{n-i}+1)}{2^n}\\&=\left[\left(1+\frac{1}{2^n}\right)\sum_{i=0}^n\binom{n}{i}\right]+\frac{1}{2^{n-1}}\sum_{i=0}^n\binom{n}{i}2^i\\&=2^n+1+\frac{3^n}{2^{n-1}} \end{align}$$

问题解决。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const LL MOD = 998244353;

int T;
LL n;

inline LL fpow(LL bs, LL idx){
	bs %= MOD;
	LL res = 1;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

int main(){
	for(read(T); T; T--){
		read(n);
		if(n == 0)	puts("4");
		else	printf("%lld\n", (fpow(2, n) + 1 + fpow(3, n) * fpow(fpow(2, n - 1), MOD - 2) % MOD) % MOD);
	}
	return 0;
}

---

1012 Set1

首先，前 $\frac{n-1}{2}$ 个答案肯定是 $0$，我们考虑 $\frac{n-1}{2}+i$ 这个数留下来的概率。

如果 $x=\frac{n-1}{2}+i$ 留下来了，考虑大于 $x$ 的数，它们一定是与某个小于 $x$ 的数一起删掉的（否则 $x$ 作为最小数不会留下来），一共 $A_{x-1}^{n-x}$ 种方案；随后小于 $x$ 的数还有些剩下的数，它们进行两两匹配即可；考虑 $n$ 个数两两匹配的方案数，$f(n)=(n-1)f(n-2)$，即第一个数选后面一个数匹配再乘上剩下 $n-2$ 个数两两匹配的方案数，解得：$f(n)=(n-1)!!$. 所以小于 $x$ 的剩下的数两两匹配的方案数为 $(x-1-n+x-1)!!=(2x-2-n)!!=(2i-3)!!$. 综上，$x$ 留下的方案数为 $A_{x-1}^{n-x}(2i-3)!!$. （添加定义 $(-1)!!=1$ ）。

对每个数算出它留下的方案数，加起来得到总方案数，除一除即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 5000005;
const LL MOD = 998244353;

int T, n;
LL fact2[N] = {1}, fact[N] = {1}, invfact[N] = {1};

inline LL fpow(LL bs, LL idx){
	bs %= MOD;
	LL res = 1;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

int main(){
	for(int i = 1; i <= 5000000; i++){
		fact[i] = fact[i-1] * i % MOD;
		invfact[i] = fpow(fact[i], MOD - 2);
		fact2[i] = fact2[i-1] * (2*i-1) % MOD;
	}
	for(read(T); T; T--){
		read(n);
		vector<LL> ans(n+1); LL sum = 0;
		for(int i = 1; i <= n / 2; i++)	ans[i] = 0;
		for(int i = 1; i <= n / 2 + 1; i++){
			int x = n/2+i;
			ans[x] = fact[x-1] * invfact[2*x-n-1] % MOD * fact2[i-1] % MOD;
			(sum += ans[x]) %= MOD;
		}
		sum = fpow(sum, MOD - 2);
		for(int i = 1; i <= n; i++)
			printf("%lld%c", ans[i] * sum % MOD, " \n"[i == n]);
	}
	return 0;
}