杂题选做（2023.9.28-2023.10.1）

杂题选做（2023.9.28-2023.10.1）

ARC106E Medals

题目描述：

你有 $n$ 个朋友，他们会来你家玩，第 $i$ 个人 $1\cdots A_i$ 天来玩，然后 $A_i+1 \cdots 2A_i$ 天不来，然后 $2A_i+1 \cdots 3A_i$ 又会来，以此类推。

每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。

你要给每个人都颁 $K$ 个奖，问至少需要多少天

$1\ \le\ N\ \le\ 18$
$1\ \le\ K\ \le\ 10^5$
$1\ \le\ A_i\ \le\ 10^5$

题目分析：

每天只能选择一个人，每个人需要被选择 $k$ 次，有一种匹配的感觉。

可以将每一个人拆成 $K$ 个点，然后每个拆出来的点都向其在的天连边，这样如果图有完美匹配那么就是合法的。

注意到一点就是我们的答案不会很大，每一个人花费 $2 \times K$ 天就可以颁奖完成。

证明可以考虑分类讨论：如果 $k \le a_i$ 显然成立，如果 $k > a_i$，则我们可以用第三轮的去补第一轮不够的，时间也是满足条件的。

所以做法就是考虑二分答案，然后建图，判断图是否有完美匹配。

但是如果我们直接建边的话复杂度就肯定爆了，可以考虑使用霍尔定理判断是否合法。

霍尔定理即：若一个二分图有完美匹配，当且仅当对于任意一个左部点的点集 $S$，设与其相连的右部点的点集为 $T$，满足 $|S| \le |T|$。

因为每一个人拆成的 $K$ 个点可以视为一体，所以在枚举左部点的点集的时候就可以做到 $2^N$ 的复杂度。

判断与其相邻的右部点的点集大小，可以考虑对于每一个时刻找出 $S_i$ 表示 $S_i$ 这些人可以在时刻 $i$ 到达，这样的话第 $i$ 天若与集合 $T$ 里的某些人有连边，当且仅当 $S_i$ 与 $T$ 交集不为空。

但是交集不为空这个东西就很难以表示，所以就容斥一下，可以考虑维护 $T_i$ 表示 $T_i$ 这些人不可以在时刻 $i$ 到达，这样对于不可以到达的集合就是 $T_i$ 的所有子集，贡献可以使用高维后缀和维护。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,k,S[40 * N],f[N],a[N];
bool chk(int mid){
	for(int i=0; i<(1<<n); i++)	f[i] = 0;
	for(int i=1; i<=mid; i++)	f[((1<<n)-1) ^ S[i]]++; 
	for(int i=1; i<=n; i++){
		for(int j=0; j<(1<<n); j++){
			if(!((j >> (i-1)) & 1))	f[j] += f[j^(1<<(i-1))];
		}
	}
	for(int i=0; i<(1<<n); i++){
		if(mid - f[i < __builtin_popcount(i) * k)	return false;
	}
	return true;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
	for(int i=1; i<=2*n*k; i++){
		for(int j=1; j<=n; j++){
			if(((i + a[j] - 1) / a[j]) % 2 == 1)	S[i] |= (1<<(j-1));
		}
	}
	int l = 1,r = 2 * n * k,ans = 1;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(chk(mid))	ans = mid,r = mid - 1;
		else	l = mid + 1;
	}
	printf("%d\n",ans);
	return 0;
}

[POI2007] ZAP-Queries

题目描述：

密码学家正在尝试破解一种叫 BSA 的密码。

他发现，在破解一条消息的同时，他还需要回答这样一种问题：

给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 $\gcd(x,y)=d$ 的二元组 $(x,y)$ 的数量。

因为要解决的问题实在太多了，他便过来寻求你的帮助。

对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^4$，$1 \leq d \leq a,b \leq 5 \times 10^4$。

题目分析：

（一道莫反的板子题）

话不多说，考虑推式子：

$$\begin{aligned} ans &= \sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y)=d] \\ &= \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(x,y) = 1] \\ &= \sum_{k=1}^{\lfloor \frac{\min(a,b)}{d} \rfloor} \mu(k) \sum_{x=1}^{\lfloor \frac{n}{dk} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{dk} \rfloor} 1 \\ &= \sum_{k=1}^{\lfloor \frac{\min(a,b)}{d} \rfloor} \mu(k) \lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor \end{aligned}$$

对最后的这个式子直接整除分块，使用线性筛预处理 $\mu$ 的前缀和。

设所有数均同阶，则复杂度为 $O(n\sqrt{n})$

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int mu[N],prime[N],s[N],tot;
bool flag[N];
void pre_work(int n){
	mu[1] = 1;
	for(int i=2; i<=n; i++){
		if(!flag[i]){
			prime[++tot] = i;
			mu[i] = -1;
		}
		for(int j=1; j<=tot && i * prime[j] <= n; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0){
				mu[i * prime[j]] = 0;
				break;
			}
			else	mu[i * prime[j]] = -mu[i];
		}
	}
	
	for(int i=1; i<=n; i++)	s[i] = s[i-1] + mu[i];
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	pre_work(50000);
	int T;scanf("%d",&T);
	while(T--){
		int a,b,k;scanf("%d%d%d",&a,&b,&k);
		a /= k,b /= k;
		int ans = 0;
		for(int l=1,r=0; l<=min(a,b); l = r + 1){
			r = min(a/(a/l),b/(b/l));
			ans += (s[r] - s[l-1]) * (a/l) * (b/l);
		}
		printf("%d\n",ans);
	}
	return 0;
}

AGC038C LCMs

题目描述：

给定一个长度为 $N$ 的数列 $A_1, A_2, A_3, \ldots, A_N$。
请你求出 $\sum_{i=1}^{N}\sum_{j=i+1}^{N}\mathrm{lcm}(A_i,A_j)$ 的值模 $998244353$ 的结果。
$1 \leq N \leq 2 \times 10^5$，$1 \leq A_i \leq 10^6$。

$1\ \leq\ N\ \leq\ 2\cdot 10^4$
$1\ \leq\ A_i\ \leq\ 1\cdot 10^6$

题目分析：

显然要使用莫比乌斯反演来解决这个问题。

首先因为 $j$ 的下界为 $i+1$ 就很烦人，可以考虑将式子化成以下的形式：

$$\frac{\sum \limits_{i=1}^n \sum \limits_{j=1}^n \textup{lcm}(A_i,A_j) - \sum \limits_{i=1}^n \textup{lcm}(A_i,A_i)}{2}$$

下面我们的问题就显然是求前面这一坨，因为我们直接对下标做就很麻烦，所以考虑对于值域套莫反，也就是设 $b_i$ 表示值为 $i$ 的数的个数，则有：

$$\begin{aligned} ans &= \sum_{i=1}^V \sum_{j=1}^V b_i \times b_j \times \frac{i \times j}{\gcd(i,j)} \\ &= \sum_{d=1}^V \sum_{i=1}^{\lfloor \frac{V}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{V}{d} \rfloor} [\gcd(i,j)=1] \frac{1}{d} b_{id} \times b_{jd} \times id \times jd \\ &= \sum_{d=1}^V \frac{1}{d} \sum_{k=1}^{\lfloor \frac{V}{d} \rfloor} \mu(k) \sum_{i=1}^{\lfloor \frac{V}{dk} \rfloor} \sum_{j=1}^{\lfloor \frac{V}{dk} \rfloor} b_{ikd} \times b_{jkd} \times ikd \times jkd \\ &= \sum_{d=1}^V d \sum_{k=1}^{\lfloor \frac{V}{d} \rfloor} k^2\mu(k) \sum_{i=1}^{\lfloor \frac{V}{dk} \rfloor} \sum_{j=1}^{\lfloor \frac{V}{dk} \rfloor} b_{ikd} \times b_{jkd} \times i \times j \end{aligned}$$

可以考虑令 $T = dk$，则有：

$$\begin{aligned} ans &= \sum_{T=1}^V T \sum_{d | T} \frac{T}{d}\mu(\frac{T}{d}) (\sum_{i=1}^{\lfloor \frac{V}{T} \rfloor} b_{iT} \times i)^2 \end{aligned}$$

这样的话对于：$\sum_{d|T} \frac{T}{d} \mu(\frac{T}{d})$ 可以预处理 $\mu$ 后类似埃氏筛对于每一个 $T$ 处理出这一些的贡献，复杂度 $O(V \log V)$

对于 $\sum_{i=1}^{\lfloor \frac{V}{T} \rfloor} b_{iT} \times i$ 可以直接枚举 $i$ 然后计算答案，复杂度是一个调和级数的，也为 $O(V \log V)$。

所以总时间复杂度就是 $O(V \log V)$ 可以通过。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 998244353;
int tot,a[N],b[N],prime[N],mu[N],f[N];
bool flag[N];
void add(int &a,int b){
	a = ((a + b)%MOD+MOD)%MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void pre_work(int n){
	mu[1] = 1;
	for(int i=2; i<=n; i++){
		if(!flag[i]){
			prime[++tot] = i;
			mu[i] = -1;
		}
		for(int j=1; j<=tot && i * prime[j] <= n; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0){
				mu[i * prime[j]] = 0;
				break;
			}
			else	mu[i * prime[j]] = -mu[i];
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=i; j<=n; j+=i){
			add(f[j],mu[i] * i % MOD);
		}
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	pre_work(1000000);
	int n;scanf("%lld",&n);
	for(int i=1; i<=n; i++){
		scanf("%lld",&a[i]);
		b[a[i]]++;
	}
	
	int ans = 0;
	int V = 1e6;
	for(int T=1; T<=V; T++){
		int tmp = 0;
		for(int i=1; i<=V/T; i++)	tmp = (tmp + b[i * T] * i % MOD)%MOD;
		tmp = tmp * tmp % MOD;
		ans = ((ans + f[T] * T %MOD * tmp%MOD)%MOD+MOD)%MOD;
	}
	
	for(int i=1; i<=n; i++)	ans = ((ans - a[i])%MOD + MOD)%MOD;
	
	printf("%lld\n",ans * power(2,MOD-2) % MOD);
	return 0;
}

[SDOI2014] 数表

题目描述：

有一张 $n\times m$ 的数表，其第 $i$ 行第 $j$ 列（$1\le i\le n$，$1\le j\le m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。

对于全部数据，$1\le n,m\le 10^5$，$1\le Q\le 2\times 10^4$。

题目分析：

这个东西直觉上是莫反，但是有一个小于等于 $a$ 的限制就很烦人，考虑先不管这个限制，看看莫反推出来的是什么。

下文推导默认 $n < m$，如果不是则交换 $n,m$ 就可以做到。

$$\begin{aligned} ans &=\sum_{i=1}^n \sum_{j=1}^m \sigma_1(\gcd(i,j)) \\ &= \sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j)=1] \sigma_1(d) \\ &= \sum_{d=1}^n \sigma_1(d) \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} \mu(k) \lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor \end{aligned}$$

可以考虑设 $T = dk$，则有：

$$\begin{aligned} ans &= \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d \mid T} \sigma_1(d) \mu(\frac{T}{d}) \end{aligned}$$

如果我们可以维护好后面这一坨的值我们就可以直接整除分块。

可以考虑离线，将询问按照 $a$ 的大小从小到大排序，并将 $\sigma_1(d)$ 从小到大排序，然后一个个地插入符合条件的 $\sigma_1(d)$，具体来说就是如果此时 $\sigma_1(d) \le a$，那么就可以直接枚举 $d$ 的所有倍数 $T$，然后将 $\sigma_1(d) \mu(\frac{T}{d})$ 贡献到 $T$ 的后面这个式子上，因为整除分块必定要支持区间查询后面这个式子的值的和，所以可以考虑使用树状数组维护。

复杂度 $O(q \sqrt{n} \log n + n \log^2 n)$，可以通过。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N = 2e5+5;
const int MOD = 1ll<<31;
struct node{
	int n,m,a,id;
}p[N];
int prime[N],tot,ans[N],sum[N],mu[N];
bool flag[N];
PII w[N];
void pre_work(int n){
	mu[1] = 1;
	for(int i=2; i<=n; i++){
		if(!flag[i]){
			prime[++tot] = i;
			mu[i] = -1;
		}
		for(int j=1; j<=tot && i * prime[j] <= n; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0){
				mu[i * prime[j]] = 0;
				break;
			}
			else mu[i * prime[j]] = -mu[i];
		}
	}
	for(int i=1; i<=n; i++){
		w[i].second = i;
		for(int j=i; j<=n; j+=i){
			w[j].first += i;
		}
	}
}
bool cmp(node a,node b){
	return a.a < b.a;
}
bool cmp2(PII a,PII b){
	return a.first < b.first;
}
int lowbit(int x){
	return x & (-x);
}
void modify(int x,int val){
//	printf("(%d,%d)\n",x,val);
	for(;x <= 100000; x+=lowbit(x))	sum[x] += val;
}
int query(int x){
//	printf("%d\n",x);
	int ans = 0;
	for(;x; x -= lowbit(x))	ans += sum[x];
	return ans;
}
int query(int l,int r){
	return query(r) - query(l-1);
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	pre_work(100000);
	
	sort(w+1,w+100000+1,cmp2);

	int now = 1;
	int q;scanf("%lld",&q);
	for(int i=1; i<=q; i++)	scanf("%lld%lld%lld",&p[i].n,&p[i].m,&p[i].a),p[i].id = i;
	
	sort(p+1,p+q+1,cmp);
	
	for(int i=1; i<=q; i++){
		while(now <= 100000 && w[now].first <= p[i].a){
			int tmp = w[now].second;
			for(int j=tmp; j<=100000; j+=tmp){
				modify(j,w[now].first * mu[j/tmp]);
			}
			++now;
		}
		
		if(p[i].n > p[i].m)	swap(p[i].n,p[i].m);
		int n = p[i].n,m = p[i].m;
		for(int l=1,r=0; l<=n; l=r+1){
			r = min(n/(n/l),m/(m/l));
			ans[p[i].id] = (ans[p[i].id] + (n/l) * (m/l) * query(l,r));
//			printf("%lld\n",ans[p[i].id]);
		}
	}
	
	for(int i=1; i<=q; i++)	printf("%lld\n",(ans[i] + MOD)%MOD);
	return 0;
}

CF1010D Mars rover

题目描述：

给定一棵有根树，令根节点为 $1$，有 $n$ 个节点。

每个节点有五种形式：AND 表示对两个子节点进行与运算，OR 表示对两个子节点进行或运算，XOR 表示对两个子节点进行异或运算，NOT 表示对子节点（只有一个）进行非运算。特殊地，IN 表示这个节点是叶子节点，它的初值（$0/1$）由读入决定。

现在，你要依次对每个叶子节点进行改变，改变其 $0/1$ 状态，并按叶节点编号顺序，分别输出改变叶节点的状态后，根节点的值是 $0$ 还是 $1$。

$2 \le n \le 10^6$

题目分析：

若当前节点为 XOR 或 NOT，则叶子节点只要改变当前节点的值必然改变。

若当前节点为 AND，则只有两个叶子节点同时为 $1$ 时改变其中一个，或者为 $0,1$ 改变那个 $0$ 才会改变当前节点的值。

若当前节点为 OR，则只有两个叶子节点同时为 $0$ 时改变其中一个，或者为 $0,1$ 改变那个 $1$ 才会改变当前节点的值。

如果改变节点 $x$ 的值会使得 $1$ 节点的值改变，也就是 $x$ 到 $1$ 路径上的每一个节点都必然是上述几种情况之一。

可以按照是否合法的情况从上到下传递标记，也就是对于每一个节点维护 $f_i$ 表示节点 $i$ 改变是否会影响到根节点。

具体实现就是先从下到上 dfs 获得每一个节点的值，然后从上到达 dfs 得到 $f_i$ 的值。

时间复杂度 $O(n)$。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int ls[N],rs[N],val[N],opt[N];
char s[N];
bool flag[N];
void dfs1(int now){
	if(ls[now])	dfs1(ls[now]);
	if(rs[now])	dfs1(rs[now]);
	if(opt[now] == 1)	val[now] = val[ls[now]] & val[rs[now]];
	if(opt[now] == 2)	val[now] = val[ls[now]] | val[rs[now]];
	if(opt[now] == 3)	val[now] = val[ls[now]] ^ val[rs[now]];
	if(opt[now] == 4)	val[now] = val[ls[now]] ^ 1;
}
void dfs2(int now){
	flag[now] = true;
	if(opt[now] == 1){
		if(val[ls[now]] == 1 && val[rs[now]] == 1)	dfs2(ls[now]),dfs2(rs[now]);
		if(val[ls[now]] == 0 && val[rs[now]] == 1)	dfs2(ls[now]);
		if(val[ls[now]] == 1 && val[rs[now]] == 0)	dfs2(rs[now]);
	}
	if(opt[now] == 2){
		if(val[ls[now]] == 0 && val[rs[now]] == 0)	dfs2(ls[now]),dfs2(rs[now]);
		if(val[ls[now]] == 0 && val[rs[now]] == 1)	dfs2(rs[now]);
		if(val[ls[now]] == 1 && val[rs[now]] == 0)	dfs2(ls[now]);
	}
	if(opt[now] == 3)	dfs2(ls[now]),dfs2(rs[now]);
	if(opt[now] == 4)	dfs2(ls[now]);
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		if(s[1] == 'A'){
			opt[i] = 1;
			scanf("%d%d",&ls[i],&rs[i]);
		}
		else if(s[1] == 'O'){
			opt[i] = 2;
			scanf("%d%d",&ls[i],&rs[i]);
		}
		else if(s[1] == 'X'){
			opt[i] = 3;
			scanf("%d%d",&ls[i],&rs[i]);
		}
		else if(s[1] == 'N'){
			opt[i] = 4;
			scanf("%d",&ls[i]);
		}
		else if(s[1] == 'I'){
			opt[i] = 5;scanf("%d",&val[i]);
		}
	}
	
	dfs1(1);
	dfs2(1);
	for(int i=1; i<=n; i++){
		if(opt[i] == 5){
			if(flag[i])	printf("%d",val[1] ^ 1);
			else	printf("%d",val[1]);
		}
	}
	return 0;
}

CF117C Cycle

题目描述：

一个 $\texttt{tournament}$ 是一个没有自环的有向图，同时，任意两个点之间有一条边连接。这就是说，对于两个点 $u,v (u\neq v)$，有一条从 $u$ 到 $v$ 的边或一条从 $v$ 到 $u$ 的边。

给你一个 $\texttt{tournament}$，请找出一个长度为 $3$ 的环。

$1 \le n \le 5000$

题目分析：

注意到这是一张竞赛图，也就是说若存在环则必然存在三元环。

这个结论可以通过数学归纳法证明，可以自行画图证明。

所以可以直接跑一遍 $dfs$，每次判断点 $u$，点 $u$ 的父亲 $fa_u$，出点 $v$ 是否构成三元环即可。

因为我们访问过一个点之后就没有必要再访问一次，所以时间复杂度为 $O(n+m)$。

题目描述：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n,sz = -1,a[N];
char G[N][N];
bool flag = false,vis[N],tag[N];
bool chk(int a,int b,int c){
	if(G[a][b] == '1' && G[b][c] == '1' && G[c][a] == '1')	return true;
	return false;
}
void dfs(int now,int fath){
	if(flag)	return;
	vis[now] = tag[now] = true;
	for(int i=1; i<=n; i++){
		if(G[now][i] == '0')	continue;
		if(!tag[i])	dfs(i,now);
		else if(vis[i]){
			printf("%d %d %d\n",now,i,fath);
			flag = true;
		}
		if(flag)	return;
	}
	vis[now] = false;
}
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)	scanf("%s",G[i]+1);
	for(int i=1; i<=n; i++)	if(!tag[i])	dfs(i,0);
	if(!flag)	printf("-1\n");
	return 0;
}

CF303B Rectangle Puzzle II

题目描述：

在 $(0, 0) \sim (n, m)$ 中找一个最大子矩形，使其包含定点 $(x, y)$，而且 $\frac{x_2 - x_1}{y_2 - y_1} = \frac{a}{b}$。如果有多个解，输出最接近 $(x, y)$ 的矩形。如果仍有多个解决方案，按 $(x_1,y_1,x_2,y_2)$ 顺序排列的字典序最小解决方案。

题目分析：

首先可以将 $a,b$ 同时除以 $\gcd(a,b)$，这样一个满足条件的矩形的边长必然为 $(a,b)$ 的倍数。

设为 $t$ 倍，则显然最大的子矩形满足 $t = \min(\lfloor \frac{n}{a} \rfloor,\lfloor \frac{m}{b} \rfloor)$

所以为了让中心点尽可能靠近 $(x,y)$ 我们可以使用扩展的想法。

也就是每次从 $(x,y)$ 分别向左右/上下扩展 $1$，这样就可以保证 $(x,y)$ 在中心点上。

有可能存在边长为奇数的情况，这种情况为了使得排列的字典序最小，要尽可能地先扩展 $x_1,y_1$。

因为必然有解，所以如果某一边不能扩展了，那么就把剩下的边长放到另一边即可。

因为注意到横纵坐标的处理方式相同，所以可以直接写一个函数分别处理即可。

代码：

点击查看代码

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
int n,m,x,y,a,b;
PII get(int x,int a,int n){
	int x1 = 0,x2 = 0;
	if(x - (a/2) >= 0 && x + (a / 2) <= n){
		x1 = x - (a / 2);
		x2 = x + (a / 2);
		if(a % 2 == 1){
			if(x1 != 0)	x1--;
			else x2++;
		}
	} 
	else{
		if(x - (a / 2) < 0)	x1 = 0,a -= x,x2 = x + a;
		else if(x + (a / 2) > n)	x2 = n,a -= (n - x),x1 = x - a;
	}
	return {x1,x2};
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&a,&b);
	int g = __gcd(a,b);a /= g,b /= g;
	
	//分横竖分别做，情况本质相同
	
	int tmp = min(n/a,m/b);
	
	PII X = get(x,tmp * a,n);
	PII Y = get(y,tmp * b,m);
	
	printf("%d %d %d %d\n",X.first,Y.first,X.second,Y.second);
	return 0;
}

CF1874C Jellyfish and EVA

题目描述：

怪物们又入侵了小镇！明日香邀请好友水母一起驾驶 EVA。

小镇上有 $n$ 座城市。所有的怪兽都在 $n$ 城市。水母和明日香目前在城市 $1$，需要前往城市 $n$ 打败怪兽。

这里有 $m$ 条路。其中第 $i$ 条路可以从城市 $a_i$ 前往城市 $b_i$。所有道路都是有向的。也就是说，使用第 $i$ 号道路无法从 $b_i$ 号城市前往 $a_i$ 号城市。有趣的是，所有道路都满足$a_i < b_i$。

驾驶 EVA 需要两人合作。然而，明日香和水母之前并没有一起接受过任何训练。

假设 EVA 目前在城市 $u$。水母和明日香都会选择一条从城市 $u$ 开始的未被破坏的道路。假设水母和明日香分别选择了以城市 $v_1$ 和 $v_2$ 为终点的道路。如果 $v_1 = v_2$，EVA成功移动到城市 $v_1$。否则，EVA 会停留在城市 $u$，并且他们选择的两条道路都会被摧毁。

EVA 目前可能在城市 $u$ （$u \neq n$）中，而从城市 $u$ 开始没有未被摧毁的道路，在这种情况下，任务将会失败。否则，如果最终到达城市 $n$，则任务成功。

每次选择道路时，水母都知道明日香会随机选择一条道路。现在，水母想知道，如果她最优化地选择道路，任务成功的最大概率是多少。

$2 \le n \le 5000$，$0 \le m \le \min(2 \cdot 10^5,\frac{n(n-1)}{2})$

题目分析：

一个显然的想法就是要预处理出来 $f[i]$ 表示从 $i$ 开始最大成功率是多少。

显然对于一条边我们越早选择其成功走过去的概率越大，所以若当前枚举到了点 $i$，对于其出点我们就可以按照 $f$ 从大到小选择。

所以我们现在其实就是要求求解：$dp[i][j]$ 表示有 $i$ 条出边，最终成功选择了按 $f$ 排序后的第 $j$ 大的概率，有了这个东西我们的 $f$ 就很好转移了。

首先无论我们最终选择了什么，按照上文的策略，我们此时选择的边必然是按 $f$ 排序后第 $1$ 大的。

所以要对 $dp[i][1]$ 转移特殊考虑。

对于其他的转移，就是考虑当前随机选择了哪一条边，然后算一下概率即可。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
vector<int> G[N],IG[N];
int n,deg[N];
double f[N],dp[N][N];
bool cmp(int a,int b){
	return f[a] > f[b];
}
void get_ans(){
	f[n] = 1;
	queue<int> q;
	for(int i=1; i<=n; i++){
		if(!deg[i])	q.push(i);
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		sort(G[now].begin(),G[now].end(),cmp);
		for(int i=0; i<(int)G[now].size(); i++){
			int to = G[now][i];
			f[now] += 1.0 * dp[G[now].size()][i+1] * f[to];
		}
		for(auto to : IG[now]){
			deg[to]--;
			if(!deg[to])	q.push(to);
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		int m;scanf("%d%d",&n,&m);
		for(int i=1; i<=m; i++){
			int from,to;scanf("%d%d",&from,&to);
			G[from].push_back(to);
			IG[to].push_back(from);deg[from]++;
		}
		
		dp[1][1] = 1;
	
		for(int i=2; i<=n; i++){
			//选择到了 1；没有选择到 1 
			dp[i][1] += 1.0 / i + 1.0 * (i-1) / i * 0;
			for(int j=2; j<=i; j++){
				//j 之前，但是选择到了 1
				dp[i][j] += 1.0 / i * 0;
				//j 之前，且没有选择到 1
				dp[i][j] += 1.0 * (j-2) / i * dp[i-2][j-2];
				//选择到了 j
				dp[i][j] += 1.0 / i * 0;
				//j 之后 
				dp[i][j] += 1.0 * (i-j) / i * dp[i-2][j-1];
			}
//			for(int j=1; j<=i; j++){
//				printf("dp[%d][%d] = %.5f\n",i,j,dp[i][j]);
//			}
		}
		
		get_ans();
		printf("%.9f\n",f[1]);
		
		for(int i=0; i<=n; i++){
			f[i] = 0;deg[i] = 0;G[i].clear();IG[i].clear();
			for(int j=0; j<=n; j++){
				dp[i][j] = 0;
			}
		}
	}
	return 0;
}

CF710F String Set Queries

题目描述：

维护一个字符串集合，支持三种操作：

1. 加字符串
2. 删字符串
3. 查询集合中的所有字符串在给出的模板串中出现的次数

操作数 $m \leq 3 \times 10^5$，输入字符串总长度 $\sum |s_i| \leq 3\times 10^5$。

本题强制在线，应该在每次输出后调用fflush(stdout)。你只有在输出上一个询问的答案后才能读入下一组询问。

题目分析：

这里写一种很让人震撼的做法。

考虑根号分治，先设置一个阈值 $B$，若插入的字符串长度小于等于 $B$ 则我们将这个字符串插入到 Trie 树中，否则就先放到一边不管。

若现在有一个查询操作。

对于长度小于等于 $B$ 的串，我们可以暴力枚举这个字符串的后缀，然后把这个后缀放到 Trie 树上匹配，因为 Trie 树的深度最多为 $B$，所以这个部分的复杂度为 $O(B|S|)$。

对于长度大于 $B$ 的串，因为串最多有 $\frac{|S|}{B}$ 个，所以可以考虑暴力做 KMP 算法，复杂度 $O(\frac{|S|^2}{B})$。

若取 $B = \sqrt{|S|}$，则时间复杂度就为 $O(|S|\sqrt{|S|})$。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
struct trie{
	int ch[N][27],val[N];
	int rt = 1,tot = 1;
	void insert(string s,int p){
		int now = rt;
		for(int i=0; i<(int)s.size(); i++){
			if(!ch[now][s[i]-'a'])	ch[now][s[i]-'a'] = ++tot;
			now = ch[now][s[i]-'a'];
		}
		val[now] += p;
	}
	int find(char *s,int len){
		int now = rt,ans = val[now];
		for(int i=0; i<len; i++){
			if(!ch[now][s[i]-'a'])	break;
			now = ch[now][s[i]-'a'];
			ans += val[now];
		}
		return ans;
	}
}Trie;
int nxt[N],sz;
char s[N];
string v[N];
int g[N];
int search(string S,string T){  //查询 S 在 T 中的出现次数 
	S = 'a' + S;  //这样的话下标就从 1 开始了 
	T = 'a' + T;  
	
	int n = S.size(),m = T.size();
	
	int ans = 0;
	
	nxt[1] = 0;
	for(int i=2,j=0; i<n; i++){
		while(j && S[i] != S[j+1])	j = nxt[j];
		if(S[j+1] == S[i])	++j;
		nxt[i] = j;
	}
	
	for(int i=1,j=0; i<m; i++){
		while(j && S[j+1] != T[i])	j = nxt[j];
		if(S[j+1] == T[i])	++j;
		if(j == n-1){
			j = nxt[j];
			++ans;
		}
	}
	return ans;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int m;scanf("%d",&m);
	while(m--){
		string S = "";
		int t;scanf("%d",&t);cin>>S;
		int len = S.size();
		for(int i=0; i<len; i++)	s[i+1] = S[i];
		if(t == 1 || t == 2){
			if(len <= 1000)	Trie.insert(S,t == 1 ? 1 : -1);
			else	v[++sz] = S,g[sz] = (t == 1 ? 1 : -1);
		}
		else{
			int ans = 0;
			for(int i=1; i<=len; i++)	ans += Trie.find(s+i,len-i+1);
			for(int i=1; i<=sz; i++){
				if(v[i].size() <= S.size())
					ans += g[i] * search(v[i],S);
			}
			printf("%d\n",ans),fflush(stdout);
		}
	}
	return 0;
} 

CF1868C Travel Plan

题目描述：

给定一颗 $n$ 个节点的二叉树，每个点有权值 $a_i \in [1,m]$，定义从 $i$ 到 $j$ 的路径的权值 $s_{i,j}$ 为路径上的最大点权。

注意给定树相当于一棵完美二叉树，按顺序编号，从某一个结点开始其余的节点全部扔掉后形成的二叉树。

求所有树（$m^n$ 种点权）的 $\sum_{i=1}^n \sum_{j=i}^n s_{i,j}$ 的和，模 $998244353$。

$1 \le n \le 10^{18}，1 \le \sum m \le 10^5$，多测 $t \le 200$。

题目分析：

既然是对于所有的路径计数，一个显然的想法就是枚举 $LCA$。

这样对于一条长度为 $len$ 的路径，若我们钦定其最大值为 $mx$，则其造成的贡献就是 $mx \times [mx^{len} - (mx-1)^{len}] \times m^{n-len}$。

所以其实我们只要知道了长度为 $len$ 的路径条数我们就可以直接计算出答案。

但是注意到如果这是一棵完美二叉树我们是会算的，所以就考虑能不能把这个看上去就很有性质的二叉树转化为完美二叉树。

注意到其实节点 $n$ 就很有分界点的感觉，所以考虑将 $1$ 到 $n$ 的这一条链整体断掉之后，剩余的所有子树都是完美二叉树。

所以剩余子树内部的贡献我们就可以直接通过预处理完美二叉树的对应的贡献算出，而剩余子树之间必然会以 $1$ 到 $n$ 的这一条链为 $LCA$，所以可以直接自底向上枚举链上的点，然后算出以当前枚举的点为根的子树内的贡献，一层层合并即可。

预处理完美二叉树的贡献就是考虑一棵深度为 $dep$ 的完美二叉树必然有两棵深度为 $dep-1$ 的完美二叉树合并而来，所以两棵子树内部的贡献可以通过先前预处理的东西得到，我们只需要知道以新合并出来的根为 $LCA$ 的答案即可，这个可以通过简单的分讨解决。

注意的一点就是我们在知道了路径条数之后统计答案的时候，不能直接使用快速幂计算，因为原本的复杂度就有点爆炸，现在又多了一个 $O(\log n)$ 的复杂度就更爆炸了，但是这个快速幂显然可以简单地递推解决掉。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000+5;
const int MOD = 998244353;
int f[N][N],pw2[100005][300],pw[N],tmp[N],ans[N],pre[N];
//f[i][j] 代表大小为 2^i-1 的完美二叉树当中，结点个数为 j 的路径条数 
void add(int &a,int b){
	a = (a + b) % MOD;
}
int get(int a,int b){
	int tot = 0;
	while(a <= b){
		a <<= 1;
		++tot;
	}
	return tot;
}
int get2(int x){
	if(x == 0) return 1;
	return pw[x-1];
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
signed main(){
	pw[0] = 1;
	for(int i=1; i<=100; i++)	pw[i] = pw[i-1] * 2 % MOD;
	
	for(int i=1; i<=100000; i++){
		pw2[i][0] = 1;
		for(int j=1; j<=200; j++)	pw2[i][j] = pw2[i][j-1] * i% MOD;
	}
	
	f[0][0] = 1;
	for(int i=1; i<=100; i++){
		f[i][0] = 1;
		for(int j=0; j<i; j++){   //这里均为小于 i 的原因是：两个子树的大小为 2^{i-1}-1 
			for(int k=0; k<i; k++){
				add(f[i][j+k+1],get2(j) * get2(k) % MOD);
			}
		}
		for(int j=1; j<=2*i; j++)	add(f[i][j],2 * f[i-1][j] % MOD);
	}
	
	int T;scanf("%lld",&T);
	while(T--){
		int n,m;scanf("%lld%lld",&n,&m);
		int now = n,len = 2;
		pre[0] = 1,pre[1] = 1;
		ans[1] = 1;
		while(now > 1){
			++len;
			//ans 记录路径条数，pre 记录祖先后代链条数 
			int bro = now ^ 1; 
			int dep = get(bro,n);   //bro 是一个大小为 2^dep - 1 的完美二叉树 
			for(int l=0; l<=len; l++){
				if(!pre[l])	break;
				for(int r=0; r<=dep; r++){
					add(ans[l+r+1],pre[l] * get2(r));
				}
			}
			for(int i=0; i<=2*dep; i++)	add(ans[i],f[dep][i]);
			
			for(int l=0; l<=len; l++)	add(tmp[l+1],pre[l]);
			for(int r=0; r<=dep; r++){
				int t = 0;
				if(r == 0)	t = 1;
				else	t = pw[r - 1];
				add(tmp[r+1],t);
			}
			tmp[1] = 1;tmp[0] = 1;
			for(int i=0; i<=len; i++)	pre[i] = tmp[i],tmp[i] = 0;
			
			now >>= 1;
		}
		int res = 0;
		int tt = power(m,n),inv = power(m,MOD-2);
		for(int i=1; i<=200; i++){
			tt = tt * inv % MOD;
			for(int mx=1; mx<=m; mx++){
				if(ans[i]){
					add(res,mx * ans[i] %MOD * (pw2[mx][i] - pw2[mx-1][i]) %MOD * tt % MOD);
				}
			}
		}
		for(int i=0; i<=200; i++) ans[i] = pre[i] = tmp[i] = 0;
		printf("%lld\n",(res + MOD) % MOD);
	}
	return 0;
}