游记&OI - 广州纪中游记 Day4

<题面链接> 提取码：7puf

Part1. 游记

果不其然还是做模拟赛……习惯就好……

莫名感觉今天是数学专场，进门就一道期望题，还好知道套路，最后忘了写线性求逆元，被卡了；

有一些奇怪的数学结论忘了，像中国剩余定理之类的？估计回去要恶补数论了……（为什么我记得之前也说过要补数论，还学了一下中国剩余定理和扩展中国剩余定理？）

最后有一道 DAG 最长反链等于二分图最大匹配的题，反正我是没有见过这个套路，还被一个 dalao 喷了“这不是基本常识吗？”

得出结论“My vegetable has explosed…”

Tab. 这篇博客也是 Day7 补的，之前的一篇因为计算机 D盘蜜汁清空了……

又及，用Typora写博客的时候换了一个主题，莫名快乐

Part2. Solution

T1. 锻造(forging)

- Experience

你看这是一道期望题，显然我们要 Dp……

于是非常轻松（或许吧）地推导出了转移方程，最后不知道直接求逆元会被卡，就没有预处理逆元，结果就出锅了……

- Solution

可以得到一个显然的 Dp 状态：f[i] 表示锻造出 i 级剑的期望花费。

我们考虑从 f[i-1],f[i-2] 推导出 f[i]，设 i 级剑锻造成功的概率为 p[i]：

我们需要一把 i-1 级剑和一把 i-2 级剑锻造出 i 级剑，即 f[i]=f[i-1]+f[i-2]；

但是假如失败了呢，有 (1-p[i]) 的概率？我们会得到一把 i-2 级剑，要再锻造 i 级剑，我们需要锻造一把 i-1 级剑，即 f[i]=f[i-1]+f[i-2]+(1-p[i])f[i-1] ；

假如又失败了？我们仍然需要一把 i-1 级剑，即 f[i]=f[i-1]+f[i-2]+(1-p)(f[i-1]+(1-p)f[i-1])……

假如一直失败，则有 f[i]=f[i-1]+f[i-2]+(1-p)(f[i-1]+(1-p)(f[i-1]....))；

定义 g[i]=f[i-1]+(1-p)g[i] ，解一下方程，可得 g[i]=f[i-1]/p ；由于 f[i]=g[i]+f[i-2]，则 f[i]=f[i-1]/p+f[i-2]；

于是我们就得到了一个状态转移方程式。

显然这里的除以 $p$ 我们需要逆元，不过这道题直接算逆元是会 TLE 的……于是我们需要预处理逆元，线性筛即可。（因为 inv(x) 是积性函数）

Q：这里的 $p$ 可能很大啊，怎么储存它的逆元呢？

A: 根据题意我们可以知道，$p=\frac {\min(c_{i-1},b_{i-2})}{c_{i-1}}$ ，把这个式子代回转移方程式：
$f_i=\frac{c_{i-1}}{\min(c_{i-1},b_{i-2})}\cdot f_{i-1}+f_{i-2}$
所以我们并不是真正预处理 $p$ 的逆元，而是预处理 $\min(c_{i-1},b_{i-2})$ 的逆元，实际规模只有 $10^7$，所以是可以储存的。

- Source

/*Lucky_Glass*/
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll MOD=998244353;
const int LIMIT=int(1e7);

int inv[LIMIT+3],prn[LIMIT/2+3];
bool vis[LIMIT+3];
int n,m,Tbx,Tby,Tcx,Tcy,Tp,nprn;
int QPow(int A,int B){
	int ret=1;
	while(B){
		if(B&1) ret=int(1ll*ret*A%MOD);
		A=(int)(1ll*A*A%MOD);
		B>>=1;
	}
	return ret;
}
void Process(){
	inv[1]=1;
	for(int i=2;i<=LIMIT;i++){
		if(!vis[i]){
			prn[++nprn]=i;
			inv[i]=QPow(i,MOD-2);
		}
		for(int j=1;j<=nprn && 1ll*i*prn[j]<=LIMIT;j++){
			vis[i*prn[j]]=true;
			inv[i*prn[j]]=(int)(1ll*inv[i]*inv[prn[j]]%MOD);
			if(i%prn[j]==0) break;
		}
	}
}
int f[10],b[10],c[10];
int main(){
	freopen("forging.in","r",stdin);
	freopen("forging.out","w",stdout);
	Process();
	scanf("%d%d%d%d%d%d%d",&n,&m,&Tbx,&Tby,&Tcx,&Tcy,&Tp);
	f[0]=m;
	b[0]=Tby+1;c[0]=Tcy+1;
	for(int i=1;i<=n;i++){
		int I=i%3,J=(i-1)%3,K=(i-2)%3;
		b[I]=int((1ll*b[J]*Tbx+Tby)%Tp+1);
		c[I]=int((1ll*c[J]*Tcx+Tcy)%Tp+1);
		if(i==1)
			f[1]=int(f[0]+1ll*f[0]*c[0]%MOD*inv[min(c[0],b[0])]%MOD)%MOD;
		else
			f[I]=int(f[K]+1ll*f[J]*c[J]%MOD*inv[min(c[J],b[K])]%MOD)%MOD;
	}
	printf("%d\n",f[n%3]);
	return 0;
}

T2. 整除(division)

- Experience

说起来也只怪自己的数学太菜了……

推出来了前大半的结论，得到了一个非常优秀的 $O(ct)\approx10^6$ 的预处理；结果不知道最后怎么统计答案（其实把那个结论推出来，就可以得到最后的答案就是把我预处理出来的所有答案乘起来），只能把算法复杂度退化到 $O(cn)$ ，相当于一个暴力……

ei……

- Solution

= P1. 第一个结论

显然，对于一个质数 $p$ ：

若 $x\equiv r\pmod p$；
则有 $(x+p)\equiv r\pmod p$；

再推广一下，若 $x^m\equiv r\pmod p$；
则有 $(x+p)^m\equiv r\pmod p$；

= P2. 第二个结论

$\text{如果 }\begin{cases} x\equiv a\pmod c\\ y\equiv b\pmod d \end{cases} \text{且 c,d 互质}\text{，则 } xy\equiv ab\pmod {cd}$

大概是不需要证明的……

= P3. 求解

知道上面两个结论我们能干什么呢？

先分析题目，发现题目其实是要让我们求解同余方程：

$x^m\equiv x\pmod {p_1p_2...p_c}$

由于 $p_1,p_2,…,p_c$ 互不相同，所以可以改为：

$\begin{cases} x^m\equiv x\pmod {p_1}\\ x^m\equiv x\pmod {p_2}\\ ...\\ x^m\equiv x\pmod {p_c}\\ \end{cases}$

即同余方程组的求解，可以用中国剩余定理。

但是还可以简化一下：

对于第一个结论，概括一下就是方程 $x^m\equiv r\pmod p$ 的解以 $p$ 为循环节（即如果 $x$ 是解，则 $(x+p)$ 也是解）。所以我们只要枚举 $x\in[1,p]$ ，判断是否是同余方程的解即可。

因为 $p_1,p_2,…p_c$ 都是互不相同的质数，所以它们两两互质。故设 $x^m\equiv x\pmod p_i$ 在 $[1,p_i]$ 内的解的个数为 $h_i$，则根据第二个结论，可以知道最后的答案即 $h_1h_2…h_c$ 。

处理出 $h_i$ 只需要枚举 $1$ 到 $p_i$ ，暴力判断是否是同余方程的解即可。但是注意要预处理 $x^m\bmod p$ 。

- Source

/*Lucky_Glass*/
#pragma GCC optimize(2)
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD=998244353,T=1e4;
int tex,cas,n,m,nprn;
int p[55],cnt[55],prn[T+5],inv[T+5];
bool vis[T+5];
int QPow(int A,int B,int C){
	int ret=1;
	while(B){
		if(B&1) ret=ret*A%C;
		A=A*A%C;
		B>>=1;
	}
	return ret;
}
void Process(){
	for(int i=2;i<=T;i==2? 3:i+2){
		if(!vis[i]) prn[++nprn]=i;
		for(int j=1;j<=nprn && 1ll*i*prn[j]<=T;j++){
			vis[i*prn[j]]=true;
			if(i%prn[j]==0) break;
		}
	}
}
int QRead(){
	int ret=0;char ch=getchar();
	while(ch<'0' || '9'<ch) ch=getchar();
	while('0'<=ch && ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();
	return ret;
}
int main(){
	freopen("division.in","r",stdin);
	freopen("division.out","w",stdout);
	Process();
	tex=QRead();cas=QRead();
	while(cas--){
		n=QRead();m=QRead();
		int ans=0;
		for(int i=1;i<=n;i++){
			p[i]=QRead();
			for(int j=1;j<=nprn && prn[j]<p[i];j++){
				inv[prn[j]]=QPow(prn[j],m,p[i]);
			}
			inv[1]=1;cnt[i]=2;
			for(int j=2;j<p[i];j==2? 3:j+2){
				if(!vis[j]){
					if(inv[j]==j)
						cnt[i]++;
				}
				for(int k=1;prn[k]<=j && k<=nprn && 1ll*j*prn[k]<p[i];k++){
					inv[j*prn[k]]=inv[j]*inv[prn[k]]%p[i];
					if(inv[j*prn[k]]==j*prn[k]) cnt[i]++;
					if(j%prn[k]==0) break;
				}
			}
		}
		ans=cnt[1];
		for(int i=2;i<=n;i++)
			ans=int(1ll*ans*cnt[i]%MOD);
		printf("%d\n",ans);
	}
	return 0;
}

T3. 欠钱(money)

- Experience

emm……这道题考试的时候看漏了一句话：“每只企鹅只会借一次钱”，错以为这道题是动态维护网络流……

最后回宿舍跟室友们交流才发现，这原来是一棵树 QwQ ，所以就从网络流简化为求链上最小值了~

听神犇讲题、看题解，然后发现，这是一道 LCT 的板子题。（板子又怎样，LCT 我没学啊）

然后 Day4 这天就没改出来这道题，Day5 因为听到讲课要讲 LCT，心血来潮就把 LCT 自学了一下，打了一道版题。于是来看这道题，但还是没有写出来（可能我对 LCT 理解不够深刻）。

最后看了题解，发现另一种解法，才终于 AC 了这道题。

（你们猜我是什么时候改的这道题？）

- Solution

=P1. 一些初始思路

动态倍增！！！

其实这是我考试的时候的想法……但是我不知道怎么更新倍增数组，然后就爆零了 TAT

思路很简单：

修改（0操作）就看作连一条从儿子a到父亲b（这里不能换方向）的边；不难发现，只有当 b 是 a 的祖先时，a 获得钱，b 才会获得钱，且数量为 a 到 b 的链上的最小值；
询问（1操作）首先判断 b 是否是 a 的祖先，再倍增求 a 到 b 的链上的最小值即可。

=P2. 倍增

根据这个思路，我们可以定义出倍增数组 pre[u][i] 表示 $u$ 的第 $2^i$ 个祖先，mn[u][i] 表示 $u$ 到 pre[u][i] 的链上的最小边权。

当我们连一条从儿子u 到父亲v 的边权为 c 的边时，我们需要更新：

1	pre[u][0]=v;mn[u][0]=c;

这个时候我们不更新其他的倍增数组，因为可能有很多更新的信息用不到，就浪费了时间。当我们要用到 pre[u][i] 或 mn[u][i] 时，我们用函数 Update(u,i) 更新：

void Update(int u,int x){
	for(int i=1;i<=x;i++){
        Update(pre[u][i-1],i-1); //因为之后会用到 pre[u][i-1] 和 mn[u][i-1]
        pre[u][i]=pre[pre[u][i-1]][i-1];
        mn[u][i]=min(mn[u][i-1],mn[pre[u][i-1]][i-1]);
    }
}

但是我们发现，这样还是太浪费了，因为倍增数组只可能扩展出新的值，而不会修改原来的值（即如果我们计算过 pre[u][i] 或 mn[u][i]，这两个值在之后就不会被修改了）。

我们对于每个 u ，储存 upd[u] 表示我们已经计算过 pre[u][0~upd[u]] 和 mn[u][0~upd[u]] ；于是 Update(u,i) 变为了：

void Update(int u,int x){
	for(int i=upd[u]+1;i<=x;i++){
        Update(pre[u][i-1],i-1); //因为之后会用到 pre[u][i-1] 和 mn[u][i-1]
        pre[u][i]=pre[pre[u][i-1]][i-1];
        mn[u][i]=min(mn[u][i-1],mn[pre[u][i-1]][i-1]);
    }
    upd[u]=x;
}

现在我们解决了动态倍增及其更新的问题了。

=P3. 并查集

但是还有一个问题——维护每个节点的深度（以便求 LCA 并进一步判断出 b 是否是 a 的祖先），于是我们想到可以用并查集！还可以顺带维护每个节点所在树的根节点。

但是需要注意并查集合并时是有顺序的，比如我们连了一条从儿子u 到父亲v 的边，就只能在并查集中把 u 合并到 v，道理非常显然（毕竟这是一棵有根树）。

维护深度……只能具体看代码了……（咕）

- Source

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5;

int n,m,ans;
int pre[N+3][20],mn[N+3][20],upd[N+3];
int mfa[N+3],mdep[N+3];

int MFa(int x){
	if(mfa[x]==x) return x;
	int res=MFa(mfa[x]);
	mdep[x]+=mdep[mfa[x]];
	return mfa[x]=res;
}
void Update(int u,int x){
	for(int i=upd[u]+1;i<=x;i++){
		Update(pre[u][i-1],i-1);
		pre[u][i]=pre[pre[u][i-1]][i-1];
		mn[u][i]=min(mn[u][i-1],mn[pre[u][i-1]][i-1]);
	}
	upd[u]=x;
}
int LCAMin(int u,int v){
	int del=mdep[u]-mdep[v],res=(1<<29);
	for(int i=19;i>=0;i--)
		if(del&(1<<i))
			del^=(1<<i),
			Update(u,i),
			res=min(res,mn[u][i]),
			u=pre[u][i];
	if(u==v) return res;
	return 0;
}
int main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) mfa[i]=i;
	for(int h=1;h<=m;h++){
		int tmp,u,v;
		scanf("%d%d%d",&tmp,&u,&v);
		u=(u+ans)%n+1;v=(v+ans)%n+1;
		if(tmp){
			if(MFa(u)!=MFa(v) || mdep[u]<=mdep[v]) ans=0;
			else ans=LCAMin(u,v);
			printf("%d\n",ans);
		}
		else{
			int val;scanf("%d",&val);
			val=(val+ans)%n+1;
			pre[u][0]=v;mn[u][0]=val;
			mfa[u]=v;mdep[u]=1;
		}
	}
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问！