牛客挑战赛60题解

A： 第三心脏

题目大意

给你 a,ba,b 两个数，要你找一个最小的 cc 满足 cc 是 aa 的倍数且 gcd⁡(b,c)=gcd⁡(a,b)\gcd(b,c)=\gcd(a,b)

思路

先说结论：直接暴力枚举 aa 的倍数判断即可。

然后讲讲原因：因为如果不满足，就要保证 bb 在跟 aa 的因子抵消之后还有可以跟你的那个产生任意的抵消。 那我们就看最特殊的质数，如果从小到大全都要抵消，那至少要是 2∗3∗5∗7∗...2*3*5*7*... 一直下去，那这样过不到多少个就肯定很大很大绝对超过 bb 范围 1e141e14 了，所以我们就直接暴力即可。

代码

#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

int T;
ll a, b;

ll gcd(ll x, ll y) {
	if (!y) return x;
	return gcd(y, x % y);
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld %lld", &a, &b);
		for (int i = 2; i <= 100; i++) if (gcd(a * i, b) == gcd(a, b)) {
			printf("%lld\n", a * i); break;
		}
	}
	
	return 0;
}

B：尖端放电

麻了这题给给我直接整开摆了

题目大意

n∗mn*m 网格上给你若干个点，然后两个点之间的中间会有一个标记，然后问你这个图上是否有一个地方有两个标记。 n,m≤1000,k≤1e5n,m\leq 1000,k\leq 1e5

思路

考虑到直接枚举点对，枚举标记点似乎都不太行，考虑从要求下手。 因为只用找一个标记，所以约等于我们只需要判断是否可行。

那你会发现没有重合标记的情况是很少的，因为你中间落在的位置只看有 2n∗2m2n*2m 个，那你要任意两个都不再同一个位置，那我们其实完全可以暴力枚举点对匹配，然后找，当枚举的数量超过 2n∗2m2n*2m 的时候，根据鸽笼原理显然就一定会有重合的，所以直接暴力即可。

代码

#include<set>
#include<queue>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

const int N = 1e5 + 100;
int T, n, m, k, x[N], y[N];
bool in[2001][2001];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &n, &m, &k);
		for (int i = 1; i <= 2 * n; i++) for (int j = 1; j <= 2 * m; j++) in[i][j] = 0;
		for (int i = 1; i <= k; i++) scanf("%d %d", &x[i], &y[i]);
		bool yes = 0;
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j < i; j++)
				if (in[x[i] + x[j]][y[i] + y[j]]) {
					printf("YES %.1lf %.1lf\n", 1.0 * (x[i] + x[j]) / 2, 1.0 * (y[i] + y[j]) / 2); yes = 1; break;
				}
				else in[x[i] + x[j]][y[i] + y[j]] = 1;
			if (yes) break;
		}
		if (!yes) {
			printf("NO\n");
		}
	}
	
	return 0;
}

C：格点染色

题目大意

有 nn 个格子，然后你在一个位置 ii 可以走到 i+1i+1 或者把它染色（要之前没有染色）并且跳到 aia_i，然后问你把所有格子都染上色有多少顺序。 aia_i 不减

思路

考虑从 aia_i 不减这个性质入手，发现你一个点 ii 之后可以涂的点是 ai∼na_i\sim n 中的。 然后你就考虑弄好前 ii 个有一个顺序了，第 i+1i+1 个要放在哪里，然后因为递增你就可以放在这些的前面，所以就是之前的方案乘 (i+1)−ai+1+1(i+1)-a_{i+1}+1。 所以就是 ∏i=1n(i−ai+1)\prod\limits_{i=1}^n(i-a_i+1) 就可以啦。

代码

#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mo 1000000007

using namespace std;

const int N = 1e6 + 100;
int n, a[N];
ll f[N];

int main() {
	scanf("%d", &n); f[0] = 1;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		f[i] = f[i - 1] * (1 + i - a[i]) % mo;
	}
	printf("%lld", f[n]);
	
	return 0;
}

D：三千道路

题目大意

给你一个有向图，然后问你是否有一个对应的竞赛图满足任意一个点到另一个点的连通性在两个图都是一样的。

思路

考虑怎样会不满足： 发现就是缩点之后存在分叉路，至于怎么具体判断呢？ 你发现可以拓扑排序，每次把没有入度的点删了，然后这个过程中不能有两个点或者以上在队列里面就行。 但是你会发现交上去锅了，因为我们少考虑了一个事情，就是环的大小如果是 22，那你两个点之间只能有一条边，但是你又要互相连通，所以也是不合法的，那这个也简单，就判一下每个环的大小即可。

代码

#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

const int N = 2e5 + 100;
struct node {
	int to, nxt;
}e[N << 1], e_[N << 1];
int T, n, m, le[N], KK, le_[N], KK_, ru[N], sz[N];
int dfn[N], low[N], sta[N], col[N], tot, tmp;
queue <int> q;

void add(int x, int y) {
	e[++KK] = (node){y, le[x]}; le[x] = KK;
}

void add_(int x, int y) {
	e_[++KK_] = (node){y, le_[x]}; le_[x] = KK_; ru[y]++;
}

void Init() {
	while (!q.empty()) q.pop();
	memset(e, 0, sizeof(e)); memset(e_, 0, sizeof(e_));
	memset(le, 0, sizeof(le)); memset(le_, 0, sizeof(le_));
	memset(ru, 0, sizeof(ru)); memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low)); memset(sta, 0, sizeof(sta));
	memset(col, 0, sizeof(col)); memset(sz, 0, sizeof(sz));
	n = m = KK = KK_ = tot = tmp = 0;
}

void tarjan(int now) {
	dfn[now] = low[now] = ++tmp; sta[++sta[0]] = now;
	for (int i = le[now]; i; i = e[i].nxt)
		if (!dfn[e[i].to]) tarjan(e[i].to), low[now] = min(low[now], low[e[i].to]);
			else if (!col[e[i].to]) low[now] = min(low[now], dfn[e[i].to]);
	if (dfn[now] == low[now]) {
		col[now] = ++tot; sz[tot] = 1;
		while (sta[sta[0]] != now) col[sta[sta[0]]] = tot, sz[tot]++, sta[0]--;
		sta[0]--;
	}
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= m; i++) {
			int x, y; scanf("%d %d", &x, &y); add(x, y);
		}
		for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
		for (int i = 1; i <= n; i++)
			for (int j = le[i]; j; j = e[j].nxt)
				if (col[i] != col[e[j].to]) add_(col[i], col[e[j].to]);
		for (int i = 1; i <= tot; i++) if (!ru[i]) q.push(i);
		bool yes = 1;
		while (!q.empty()) {
			if (q.size() > 1) {
				printf("NO\n"); yes = 0; break;
			}
			int now = q.front(); q.pop();
			for (int i = le_[now]; i; i = e_[i].nxt) {
				ru[e_[i].to]--; if (!ru[e_[i].to]) q.push(e_[i].to);
			}
		}
		if (yes) {
			for (int i = 1; i <= tot; i++)
				if (sz[i] == 2) {
					yes = 0; printf("NO\n"); break;
				}
		}
		if (yes) printf("YES\n");
		Init();
	}
	
	return 0;
}

E：字典树简单题

题目大意

给你一个 01 Trie，在线操作会从一个点为根节点插入一个 01 串，或者询问以一个点为根节点到哪个叶子节点形成的01串对应数的值是所有能形成的串的值中第 k 小的。 （保证不会有子串关系）

思路

首先有一个很暴力的方法就是 LCT 维护然后 Splay 维护子树大小，而这也是 std 的做法。 不过后来被一种方法过了，然后我就用了这种。

就是你考虑如果没有分叉是肯定走向的所以我们只需要维护有分叉的点，然后因为插入 01 串的长度和不会超过一个值所以你分叉数量是 ∑k\sqrt{\sum k} 的级别的（因为一个分叉只能分叉两个） 然后还有一个性质就是你往下走的字典序一定是优于往上再往下的。 （因为你往上再往下一定要 01/1001/10，而往下走只需要一个，形成的数肯定是比下面的大）

所以你就可以用一个类似虚树的感觉维护那些特殊的（11 号点，叶子节点和有分叉的点，可以动态维护） 然后每次查询就跳大小跳到一个子树叶子节点大小大于等于 kk 的，然后再 log⁡sz\log sz 往里找即可。

代码

#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

const int N = 6e5 + 100;
int n, m, d, lastans, sz[N], fa[N], fap[N];
int son[N][2], deg[N], ls[N], rs[N];
char s[N];

int dfs1(int now, int father, int father_p) {
	fa[now] = father; fap[now] = father_p;
	if (!son[now][0] && !son[now][1]) {
		sz[now] = 1;
		return now;
	}
	int lson = 0, rson = 0;
	if (now == 1 || (son[now][0] && son[now][1])) father = now;
	if (son[now][0]) lson = dfs1(son[now][0], father, (father == now) ? 0 : father_p);
	if (son[now][1]) rson = dfs1(son[now][1], father, (father == now) ? 1 : father_p);
	if (now == 1 || (son[now][0] && son[now][1])) {
		ls[now] = lson; rs[now] = rson; return now;
	}
	return lson + rson;
}

void dfs2(int now, int father, int father_p) {
	if (fa[now] != fa[father]) return ;
	if (now != father) fa[now] = father, fap[now] = father_p;
	if (sz[now]) (father_p ? rs[father] : ls[father]) = now;
	if (son[now][0]) dfs2(son[now][0], father, (now == father) ? 0 : father_p);
	if (son[now][1]) dfs2(son[now][1], father, (now == father) ? 1 : father_p);
}

int main() {
	scanf("%d %d %d", &n, &m, &d);
	for (int i = 2; i <= n; i++) {
		int x, y; scanf("%d %d", &x, &y); son[x][y] = i;
		deg[i] = deg[x] + 1;
	}

	dfs1(1, 0, 0);
	for (int i = n; i > 1; i--) sz[fa[i]] += sz[i];
	
	while (m--) {
		int op, x;
		scanf("%d %d", &op, &x); x ^= lastans;
		if (op == 1) {
			scanf("%s", s + 1); int len = strlen(s + 1);
			int now = x; for (int i = 1; i <= len; i++) {
				son[now][s[i] - '0'] = ++n; deg[n] = deg[now] + 1;
				now = son[now][s[i] - '0']; fa[now] = fa[x];
			}
			sz[now] = 1;
			dfs2(x, x, -1); (fap[x] ? rs[fa[x]] : ls[fa[x]]) = x;
			sz[x] = sz[ls[x]] + sz[rs[x]]; while (fa[x]) x = fa[x], sz[x] = sz[ls[x]] + sz[rs[x]];
		}
		else {
			int k; scanf("%d", &k);
			if (!sz[x]) x = (fap[x] ? rs[fa[x]] : ls[fa[x]]);
			int lst = 0;
			while (sz[x] < k) lst = x, x = fa[x];
			if (lst) {
				k -= sz[lst]; if (lst == rs[x]) x = ls[x]; else x = rs[x];
			}
			while (sz[x] > 1) {
				if (sz[ls[x]] < k) k -= sz[ls[x]], x = rs[x]; else x = ls[x];
			}
			lastans = x; printf("%d\n", lastans);
		}
	}
	
	return 0;
}

F：再见***与胖头鱼

题目大意

有 nn 个胖头鱼，一开始都有圣盾，攻击权重都是 11，然后攻击力都是 88。 然后你每次会根据攻击权重选一个胖头鱼打，如果有然后收到他攻击力的伤害，如果有圣盾就会给自己加 aa 的攻击力才攻击而且给其它鱼圣盾，自己的会破掉，然后攻击权重加一。 如果一次攻击没有攻击到这条鱼，那其攻击权重会变回 11。 然后要你对于 1∼m1\sim m 分别求出攻击 ii 次你期望受到的伤害。

思路

首先一个重要的点就是谁破盾无所谓，因为你是期望伤害，每次的期望伤害只跟破盾次数有关。 那我们考虑根据这个来进行一个多项式的推。

F(x)F(x)：攻击 ii 次+换人（但是可以换的个数不确定所以上面部分不乘法） F(x)[i]=i!(n−1)!(n+i−1)!1n+iF(x)[i]=\dfrac{i!(n-1)!}{(n+i-1)!}\dfrac{1}{n+i} （用递推求）

F′(x)F'(x)：攻击 ii 次（最后） F(x)[i]=i!(n−1)!(n+i−1)!F(x)[i]=\dfrac {i!(n-1)!}{(n+i-1)!} （也是递推求）

H(x)H(x)：攻击同一个胖头鱼中间隔着 ii 次的概率。 H(x)=(n−1)F(x)∑i=0∞(n−2)F(x)i=(n−1)F(x)(n−2)(1−F(x))H(x)=(n-1)F(x)\sum\limits_{i=0}^{\infty}(n-2)F(x)^i=\dfrac{(n-1)F(x)}{(n-2)(1-F(x))} （注意这里的 n−1n−2\dfrac{n-1}{n-2} 常数项是不能乘的，所以你可以现在 F(x)F(x) 和 1−F(x)1-F(x) 里面给对应的项乘了再除）

fi,jf_{i,j} 为 ii 次圣盾破碎，打了 jj 次的概率。 fi(x)=(H(x)+1)(F(x)H(x))i−1F′(x)f_i(x)=(H(x)+1)(F(x)H(x))^{i-1}F'(x)（一开始可以不是它，也可以是它，就是 H(x)+1H(x)+1）

然后答案就是这个： ∑i=1n∑j=1∞j×fi,j\sum\limits_{i=1}^n\sum\limits_{j=1}^{\infty}j\times f_{i,j}

（a=0a=0 且初始 00） ANS(x)=∑fi(x)=(H(x)+1)F′(x)∑i=1∞i(F(x)H(x))i−1ANS(x)=\sum\limits f_{i}(x)=(H(x)+1)F'(x)\sum\limits_{i=1}^{\infty}i(F(x)H(x))^{i-1} ANS(x)=(H(x)+1)F′(x)1(1−F(x)H(x))2ANS(x)=(H(x)+1)F'(x)\dfrac{1}{(1-F(x)H(x))^2}

然后这个下面的平方是这么推的： 其实就是求这个 ∑i=1∞ixi−1\sum\limits_{i=1}^{\infty}ix^{i-1}。 然后 ∑i=1∞xi=11−x\sum\limits_{i=1}^{\infty}x^i=\dfrac{1}{1-x} 然后给它求导：∑i=1∞ixi−1=1(1−x)2\sum\limits_{i=1}^{\infty}ix^{i-1}=\dfrac{1}{(1-x)^2} 就是这个啦！

然后多项式搞就完了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 998244353
#define clr(f, n) memset(f, 0, (n) * sizeof(int))
#define cpy(f, g, n) memcpy(f, g, (n) * sizeof(int))

using namespace std;

const int N = 200000 * 8 + 1;
int n, m, a, an[N], inv[N], G, Gv;
int F[N], F_[N], T[N], H[N];

int jia(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int jian(int x, int y) {return x - y < 0 ? x - y + mo : x - y;}
int cheng(int x, int y) {return 1ll * x * y % mo;}
int ksm(int x, int y) {int re = 1; while (y) {if (y & 1) re = cheng(re, x); x = cheng(x, x); y >>= 1;} return re;}

void Init() {
	G = 3; Gv = ksm(G, mo - 2);
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = cheng(inv[mo % i], mo - mo / i);
}

void get_an(int limit, int l_size) {
	for (int i = 0; i < limit; i++)
		an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1)); 
}

void NTT(int *f, int limit, int op) {
	for (int i = 0; i < limit; i++) if (an[i] < i) swap(f[an[i]], f[i]);
	for (int mid = 1; mid < limit; mid <<= 1) {
		int Wn = ksm(op == 1 ? G : Gv, (mo - 1) / (mid << 1));
		for (int R = (mid << 1), j = 0; j < limit; j += R) {
			int w = 1;
			for (int k = 0; k < mid; k++, w = cheng(w, Wn)) {
				int x = f[j | k], y = cheng(w, f[j | mid | k]);
				f[j | k] = jia(x, y); f[j | mid | k] = jian(x, y);
			}
		}
	}
	if (op == -1) {
		int limv = ksm(limit, mo - 2);
		for (int i = 0; i < limit; i++) f[i] = cheng(f[i], limv);
	}
}

void px(int *f, int *g, int limit) {
	for (int i = 0; i < limit; i++)
		f[i] = cheng(f[i], g[i]);
}

void times(int *f, int *g, int n, int m) {
	static int tmp[N];
	int limit = 1, l_size = 0; while (limit < n + n) limit <<= 1, l_size++;
	cpy(tmp, g, n); clr(tmp + n, limit - n);
	get_an(limit, l_size);
	NTT(f, limit, 1); NTT(tmp, limit, 1);
	px(f, tmp, limit); NTT(f, limit, -1);
	clr(f + m, limit - m); clr(tmp, limit);
}

void invp(int *f, int n) {
	static int w[N], r[N], tmp[N];
	w[0] = ksm(f[0], mo - 2);
	int limit = 1, l_size = 0;
	for (int len = 2; (len >> 1) <= n; len <<= 1) {
		limit = len; l_size++; get_an(limit, l_size);
		cpy(r, w, len >> 1);
		cpy(tmp, f, limit); NTT(tmp, limit, 1);
		NTT(r, limit, 1); px(r, tmp, limit);
		NTT(r, limit, -1); clr(r, limit >> 1);
		cpy(tmp, w, len); NTT(tmp, limit, 1);
		NTT(r, limit, 1); px(r, tmp, limit);
		NTT(r, limit, -1);
		for (int i = (len >> 1); i < len; i++)
			w[i] = jian(cheng(w[i], 2), r[i]);
	}
	cpy(f, w, n); clr(w, limit); clr(r, limit); clr(tmp, limit);
}

void dao(int *f, int n) {
	for (int i = 1; i < n; i++)
		f[i - 1] = cheng(f[i], i);
	f[n - 1] = 0;
}

void jifen(int *f, int n) {
	for (int i = n; i >= 1; i--)
		f[i] = cheng(f[i - 1], inv[i]);
	f[0] = 0;
}

void mof(int *f, int n, int *g, int m) {
	static int f_[N], g_[N];
	int L = n - m + 1;
	reverse(f, f + n); cpy(f_, f, L); reverse(f, f + n); 
	reverse(g, g + m); cpy(g_ , g, L); reverse(g, g + m);
	invp(g_, L); times(g_, f_, L, L); reverse(g_, g_ + L);
	
	times(g, g_, n, n);
	for (int i = 0; i < m - 1; i++) g[i] = jian(f[i], g[i]);
	clr(g + m - 1, L);
	cpy(f, g_, L); clr(f + L, n - L);
}

void lnp(int *f, int n) {
	static int g[N];
	cpy(g, f, n); dao(g, n);
	invp(f, n); times(f, g, n, n);
	jifen(f, n - 1); clr(g, n);
}

void exp(int *f, int n) {
	static int w[N], ww[N];
	ww[0] = 1;
	int len;
	for (len = 2; (len >> 1) <= n; len <<= 1) {
		cpy(w, ww, len >> 1); lnp(w, len);
		for (int i = 0; i < len; i++)
			w[i] = jian(f[i], w[i]);
		w[0] = jia(w[0], 1);
		times(ww, w, len, len);
	}
	len >>= 1;
	cpy(f, ww, n); clr(ww, len); clr(w, len);
}

void ksmp(int *f, int n, int k) {
	lnp(f, n);
	for (int i = 0; i < n; i++) f[i] = cheng(f[i], k);
	exp(f, n);
}

int main() {
	Init();
	
	scanf("%d %d %d", &n, &m, &a);
	
	H[0] = 1; F_[1] = 1;
	for (int i = 1; i <= m; i++) {
		int invs = ksm(n + i, mo - 2);
		F[i] = cheng(F_[i], cheng(invs, n - 1));
		H[i] = jian(0, cheng(cheng(F_[i], invs), n - 2));
		F_[i + 1] = cheng(cheng(F_[i], i + 1), invs);
	}
	invp(H, m + 1);
	times(H, F, m + 1, m + 1);
	for (int i = 1; i <= m; i++) F[i] = cheng(F[i], ksm(n - 1, mo - 2));
	
	cpy(T, F, m + 1); times(T, H, m + 1, m + 1);
	for (int i = 0; i <= m; i++) T[i] = jian((i == 0), T[i]);
	times(T, T, m + 1, m + 1); invp(T, m + 1);
	times(T, F_, m + 1, m + 1);
	H[0] = jia(H[0], 1); times(T, H, m + 1, m + 1); H[0] = jian(H[0], 1);
	
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		ans = jia(ans, cheng(T[i], a));
		printf("%d\n", jia(ans, cheng(8, i)));
	}
	
	return 0;
}