LGR-143-解题-526互联

A. 三个数

DESCRIPTION

有一个有 \((w-2)\) 个数的集合 \(S=\{3,4,5,\cdots ,w\}\)。
要求构造一个只包含非负整数的集合（无重复元素），使得 \(S\) 里面的任何一个数都能被这个集合里面大于等于 \(3\) 个不同的数相加得到，求这个集合中至少包含多少个元素。

SOLTION

对于 \(w = 3\) 是，可以发现，\(3\) 有且只可以被 \(\left\{0,1,2\right\}\) 表示出来。
推广到更大的情况，\(\left\{0,1,2,3\right\}\) 最大可以表示为 \(6\)，但是 \(\left\{0,1,2,4\right\}\) 无法表达出 \(4\) 来。

以此类推，下一个数一定是前面数的和，即前一个数的两倍。

正确性类似与，倍增的写法。

判断：将每个集合的和 \(s\) 纪录下来，使得 \(x\) 一定能被表示出来满足 \(x \le s\)，时间复杂度为 \(\mathcal O(T\log w)\)。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int K = 43;

int c[1001000], t, w, tmp;

signed main() {
	c[1] = 0; c[2] = 1; c[3] = 2; c[4] = 3;
	for (int i = 5; i < K; i ++ ) {
		c[i] = c[i - 1] << 1; 
	}
	for (int i = 0; i < K; i ++ ) {
		c[i] = c[i - 1] + c[i];
	}
	scanf("%lld",&t);
	while (t -- )  {
		scanf("%lld",&w);
		tmp = lower_bound(c, c + K, w) - c;
		cout << tmp << '\n'; 
	}	
	return 0;
}

B. 一些数

DESCRIPTION

钦定一些位置的值，问有多少长度为 \(n\) 的排列满足条件，且最长上升序列的长度为 \(n-1\).

SOLTION

最长上升子序列的长度为 \(n-1\)，就相当于将这个数列 \((p_i=i)\) 的一个数重新插入到序列的其他位置所得的的序列。

对于给出的 \(x_i\) 与 \(y_i\)，大型分类讨论的第 \(2\) 题！。。。

如果所有 \(x_i = y_i\)，就说明其中的改变，仅存在与每个 \(x_i\) 之间，这样的贡献为 \((x_i-x_{i-1}-2)^2\)。
如果出现 \(\left|x_i-y_i\right|\ge 2\)，那么这样的序列尤其最多只会存在一个，暴力 \(\mathcal O(n)\) 判断即可。
- 对于相邻的两个数 \(k_{i},k_{i+1}\) 交换的情况，也是相同的。
如果仅出现一段连续的 \(x_i=y_i+1\)，那么答案为 \((y_s-y_{s-1}-1)(y_{t+1}-y_t)\)；
- 是将，这段连续的区间的开头 \(l\) 与它前面的 \(x_{st}=y_{st}\) 的 \(st\) 之间选择一个数 \(x\)，共 \((l - st + 1)\) 种。
- 在这段的结尾 \(r\)，与它后面的 \(x_{ed}=y_{ed}\) 的之间的间隔中选择一个，共 \((ed-r)\) 种。
相对应的，如果仅出现一段连续的 \(x_i=y_i-1\)，那么答案为 \((y_s-y_{s-1})(y_{t+1}-y_t-1)\)，同上。

CODE

// jiji...
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int KI = 1e6 + 6;

inline int read() {
	int x = 0; bool f = false; char c = getchar();
	while (!isdigit(c)) {f |= (c == '-'); c = getchar();}
	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}
	return f ? -x : x; 
}

int n, q, ans, x[KI], y[KI], k[KI], l, r, tmp, st, ed;
bool flag1, flag2, flag3;

int ksm(int a, int k) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = ans * a;
		a = a *a; k >>= 1;
	} 
	return ans;
}

bool check() {
	int fvr = 0;
	for (int i = 1; i <= q; i ++ ) {
		if (abs(x[i] - y[i]) > 1) {
			if (!fvr) fvr = i;
			else return false;
		}
	}
	if (fvr) {
		bool f1 = false, f2 = false;
		if (x[fvr] > y[fvr]) {
			for (int i = 1; i <= n; i ++ ) {
				if (!k[i]) continue;
				if (i >= y[fvr] && i < x[fvr] && k[i] != i + 1)  return false;
				if ((i < y[fvr] || i > x[fvr]) && k[i] != i) return false;
			}
		}
		else { 
			for (int i = 1; i <= n; i ++ ) {
				if (!k[i]) continue;
				if ((i > y[fvr] || i < x[fvr]) && k[i] != i)  return false;
				if ((i <= y[fvr] && i > x[fvr]) && k[i] != i - 1) return false;
			}
		}
		return true;
	}
	else {
		flag2 = false;
		for (int i = 1; i <= n; i ++ ) {
			if (!k[i] || k[i] == i) continue;
			if (k[i] == i + 1 && k[i + 1] == i) {
				if (flag2 == false) flag2 = true;
				else return false;
			}
		}
		return flag2;
	}
}

void sol() {
	n = read(); q = read();
	for (int i = 1; i <= n; i ++ ) k[i] = 0; 
	flag1 = flag2 = false;
	for (int i = 1; i <= q; i ++ ) {
		x[i] = read(); y[i] = read();
		k[x[i]] = y[i];
		if (x[i] != y[i]) flag1 = true;
	}
	if (flag1 == false) {
		ans = 1;
		for (int i = 1; i <= q; i ++ ) {
			ans = ans * ksm(x[i] - x[i - 1] - 2, 2);
		}
		ans = ans * ksm(n + 1 - x[q] - 2, 2); 
		cout << ans << '\n';
		return ;
	}
	if (check() == true) cout << 1 << '\n';
	else {
		flag2 = flag3 = false;
		l = INT_MAX; r = INT_MIN;
		tmp = st = 0; ed = n + 1;
		for (int i = 1; i <= n; i ++ ) {
			if (!k[i]) continue;
			if (k[i] == i) {
				if (flag2 == false) tmp = k[i];
				else if (flag2 && !flag3) {ed = k[i]; flag3 = true;}
			}
			else if (k[i] - 1 == i) { 
				if (flag2 && flag3) {
					cout << 0 << '\n';
					return ;
				}
				l = min(l, k[i]); r = max(r, k[i]); 
				flag2 = true; st = tmp;
			}
		}
		if (flag2 == true) {
			cout << (l - st) * (ed - r - 1) << '\n';
			return ; 
		}
		else {
			flag2 = flag3 = false; 
			tmp = st = 0; ed = n + 1; 
			for (int i = 1; i <= n; i ++ ) {
				if (!k[i]) continue;
				if (k[i] == i) {
					if (flag2 == false) tmp = k[i];
					else if (flag2 && !flag3) {ed = k[i]; flag3 = true;}
				}
				else if (k[i] + 1 == i) {
					if (flag2 && flag3) {
						cout << 0 << '\n';
						return ;
					}
					l = min(l, k[i]); r = max(r, k[i]); 
					flag2 = true; st = tmp;
				}
			}
			
			if (flag2) cout << (l - st - 1) * (ed - r) << '\n';
			else cout << 0 << '\n'; 
			return ;
		}
	}
}

signed main() {
	int T = read();
	while (T -- ) sol();
	return 0;
}

C. 一棵树

DESCRIPTION

给定一颗树，每个点上有权值 \(a_i\)。定义路径 \((x,y)\) 的权值为 \(w(x,y)=\overline{a_x\dots a_y}\) 。
求 \(\sum_{i=1}^{n}\sum_{j=1}^{n}w(i,j)\)。

SOLTION

令 \(k_i\) 为 \(a_i\) 的位数（tip：\(0\) 的位数为 \(1\)）。

对于树退化到链。

考虑以 \(a_i\) 作为结尾时的贡献，设 \(f_i\) 为以 \(a_i\) 作为结尾，\(1\dots i\) 的任意数作为开始时的贡献。

（由于 \(w(x,y) \not= w(y,x)\)，所以需要将链反过来再进行一遍计算）

在以 \(a_i\) 结尾的，并且以\(1\dots i\) 的任意数作为开始的序列的序列共有 \(i\) 个，

那么有，

\[f_i=f_{i-1}\times 10^{k_{i}} + a_i\times i \]

对于树到星图。

对于路径长度为 \(1\) 的，求 \(\sum_{i=1}^{n}a_i\) 即可。
对于路径长度为 \(2\) 的，
- 以 \(1\) 为起点的，其中叶子节点的贡献为 \(\sum_{i=2}^{n}a_i\)，节点 \(1\) 的贡献为 \(\sum_{i=2}^{n}a_1\times 10^{k_i}\)。
- 以 \(1\) 为终点的，其中叶子节点的贡献为 \(\sum_{i=2}^{n}a_i\times10^{k_1}\)，节点 \(1\) 的贡献为 \(a_1\times(n-1)\)。
对于路径长度为 \(3\) 的，
- 以 \(a_i(i\not=1)\) 为终点，那么节点 \(1\) 的贡献为 \(a_1\times10^{k_i}\times(n-2)\)，节点 \(i\) 的贡献为 \(a_i\)，其他节点的贡献为 \(\sum_{j\not=1\and j\not=i}a_j\times10^{k_i+k_1}\)。

对于树的情况。

如同链的情况一样，设 \(f_u\) 为以 \(a_u\) 作为结尾，\(u\) 子树里的任意数作为开始时的贡献。

那么有，

\[f_u=\left(\sum_{v\in son_u}f_v\right)\times10^{k_u}+a_u\times size_u \]

对于每一个点 \(i\) 来讲，求一遍是 \(\mathcal O(n^2)\) 的，可以换根做到 \(\mathcal O(n)\) 的时间复杂度。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int KI = 3e6 + 7;
const int mod = 998244353;

inline int read() {
	int x = 0; bool f = false; char c = getchar();
	while (!isdigit(c)) {f |= (c == '-'); c = getchar();}
	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}
	return f ? -x : x; 
}

int k[KI], a[KI], n;
int dep[KI], siz[KI], tmpsiz, tmp, sum, rot, ans, f[KI];
int to[KI], hd[KI], nxt[KI], cnt;

int ksm(int a, int k) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = ans * a %mod;
		a = a * a %mod; k >>= 1; 
	}
	return ans;
}

/*************************************************/

void sol_chain() {
	tmp = 0; ans = 0;
	for (int i = 1; i <= n; i ++ ) {
		tmp = ((tmp * ksm(10, k[i]) %mod) + (a[i] * i %mod)) %mod;
		ans = (ans + tmp) %mod;
	}
	tmp = 0; 
	for (int i = n; i >= 1; i -- ) {
		tmp = ((tmp * ksm(10, k[i]) %mod)+ (a[i] * (n - i + 1) %mod)) %mod;
		ans = (ans + tmp) %mod;
	}
	for (int i = 1; i <= n; i ++ ) ans = ((ans - a[i]) %mod + mod) %mod;
	cout << ans << '\n';
	return ;
}

/*************************************************/

void sol_star() {
	sum = 0; ans = 0;
	for (int i = 1; i <= n; i ++ ) {
		ans = (ans + (a[i] * n %mod)) %mod;
	}
	for (int i = 2; i <= n; i ++ ) {
		ans = (ans + (ksm(10, k[1]) * a[i] %mod)) %mod;
		ans = (ans + ((ksm(10, k[i]) * a[1] %mod) * (n - 1) %mod) ) %mod; 
		sum = (sum + ksm(10, k[i] + k[1])) %mod;
	}
	for (int i = 2; i <= n; i ++ ) {
		tmp = ((sum - ksm(10, k[i] + k[1])) %mod + mod) %mod;
		ans = (ans + (tmp * a[i] %mod)) %mod;
	}
	cout << ans << '\n';
	return ;
}

/*************************************************/

void init(int u, int fa) {
	siz[u] = 1;
	int tmp = 0; 
	for (int i = hd[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v == fa) continue;
		init(v, u);
		siz[u] += siz[v]; 
		tmp = (tmp + f[v]) %mod;
	}
	f[u] = ((tmp * ksm(10, k[u]) %mod) + (a[u] * siz[u] %mod)) %mod;
}

void dfs(int u, int fa) {
	int tmp = 0; 
	for (int i = hd[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v == fa) continue;
		tmp = (tmp + f[v]) %mod;
	}
	if (u != 1) {
		f[u] = (((((f[fa]-f[u]*ksm(10, k[fa])%mod)%mod+mod)-a[fa]*siz[u]+tmp)%mod+mod)%mod * ksm(10, k[u]) %mod) + (a[u] * n) %mod;
	}
	for (int i = hd[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v == fa) continue;
		dfs(v, u);
	}
}

void sol_tree() {
	init(1, 0); dfs(1, 0); 
	for (int i = 1; i <= n; i ++ ) {
		ans = (ans + f[i]) %mod;
	}
	cout << ans << '\n';
	return ; 
}

/*************************************************/

void addedge(int u, int v) {
	to[++ cnt] = v;
	nxt[cnt] = hd[u];
	hd[u] = cnt;
	return ; 
}

signed main() {
	n = read();
	for (int i = 1, tmp; i <= n; i ++ ) {
		tmp = a[i] = read();
		if (!tmp) k[i] = 1;
		while (tmp) {
			k[i] ++; tmp /= 10;
		}
	}
	for (int u = 2, v; u <= n; u ++ ) {
		v = read();
		addedge(u, v); addedge(v, u);
	}
	sol_tree(); 
	return 0;
}

D. 好多数

DESCRIPTION

定义“ \(n\) 号数学树”为一颗根节点权值为 \(n=\prod a_i^{b_i}\) 的树，其中对于任意权值 \(k\) 的节点，其儿子的权值为 \(k\) 的因子 \(x\notin \left\{1,k\right\}\)。
多次询问权值为 \(x\) 的节点数。

SOLTION

对于每个 \(x\) 将其写作 \(\prod a_i^{c_i}\) 的形式（质因数分解）。

那么向上跳父亲的过程可以表示为：将某些 \(c_i\) 进行增大，直到所有的 \(c_i=b_i\)。

设深度为 \(i\) 的 \(x\) 总共有 \(f_i\) 个，那么最终答案即为 \(\sum f_i\)。

对于每个因数，设 \(g_{i,j}\) 表示为跳了 \(i\) 次，值增加了 \(j\) 的方案数，利用插板法，得到

\[g_{i,j} = \binom{j + i - 1}{i - 1} \]

设 \(h_i\) 表示包含空选时深度为 \(i\) 的方案数，即

\[h_i=\prod_{j=1}^{cnt}g_{i,b_j-c_j} \]

那么 \(f_i\) 即为 \(h_i\) 去掉空选的情况，容斥即可。

\[f_i=h_i-\sum_{j=1}^i f_{i-j} \]

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e4 + 7, mod = 998244353;
int n, ans, cnt, x, q;
int jc[N], inv[N], f[N], a[N], b[N], c[N];

int ksm(int a, int k) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = ans * a %mod;
		a = a * a %mod; k >>= 1;
	}
	return ans;
}

int C(int n, int m) {
	return (jc[n] * inv[m] %mod) * inv[n - m] %mod;
}

signed main() {
	jc[0] = 1;
	for (int i = 1; i < N; i ++ ) jc[i] = (jc[i - 1] * i) %mod;
	inv[N - 1] = ksm(jc[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i -- ) {
		inv[i] = (inv[i + 1] * (i + 1)) %mod;
	}
	n = 1;
	while (scanf("%lld%lld",&a[n],&b[n]) != EOF) {
		if (!a[n] && !b[n]) { n -- ; break;}
		n ++;
	} 
	scanf("%lld",&q);
	while (q -- ) {
		scanf("%lld",&x);
		ans = cnt = 0;
		if (x == 1) {
			cout << 0 << ' '; continue;
		}
		for (int i = 1; i <= n; i ++ ) {
			c[i] = b[i];
			while (x % a[i] == 0 && c[i]) {
				x /= a[i]; c[i] -- ;
			}
			cnt += c[i];
		}
		if (x > 1) {cout << 0 << ' '; continue;}
		if (cnt == 0) {cout << 1 << ' '; continue;}
		for (int i = 1; i <= cnt; i ++ ) {
			f[i] = 1;
			for (int j = 1; j <= n; j ++ ) {
				if (c[j]) f[i] = f[i] * C(c[j] + i - 1, i - 1) %mod;
			}
			for (int j = 1; j < i; j ++ ) {
				f[i] = ((f[i] - f[j] * C(i, j)) %mod + mod) %mod;
			}
			ans = (ans + f[i]) %mod;
		}
		cout << ans << ' ';
	}
	return 0;
}