BZOJ 2759: 一个动态树好题

传送门
数论与数据结构相结合的好题.

如果,我们令i向p[i]连一条有向边的话,这个有向图一定会有环,形成基环外向森林.如图:如果,我们令i向p[i]连一条有向边的话,这个有向图一定会有环,形成基环外向森林.如图:在这里插入图片描述
既然一定有环,那么变量就会循环,对于一个长度为tt的环,可以得到以下方程组:
{x1≡k1∗xt+b1(mod⁡10007)x2≡k2∗x1+b2(mod⁡10007)……xt≡kt∗xt−1+bt(mod⁡10007)egin{cases}x_1≡k_1*x_t+b_1(operatorname{mod} 10007) \x_2≡k_2*x_1+b_2(operatorname{mod} 10007)\……\x_t≡k_t*x_{t-1}+b_t(operatorname{mod} 10007)end{cases}

这个方程组怎么解,当然是整体代入啦.

{x1≡k1∗xt+b1(mod⁡10007)x2≡k2∗x1+b2≡k2∗(k1∗xt+b1)+b2≡k1∗k2∗xt+b1∗k2+b2(mod⁡10007)x3≡k3∗x2+b3≡k3∗(k1∗k2∗xt+b1∗k2+b2)+b3≡k1∗k2∗k3∗xt+b1∗k2∗k3+b2∗k3+b3(mod⁡10007)……xt≡kt∗xt−1+bt≡(∏i=1tki)+∑i=1t(bi∗∏j=i+1tkj)(mod⁡10007)(数学归纳法)egin{cases}x_1≡k_1*x_t+b_1(operatorname{mod} 10007) \x_2≡k_2*x_1+b_2≡k_2*(k_1*x_t+b_1)+b2≡k_1*k_2*x_t+b_1*k_2+b_2(operatorname{mod} 10007)\x_3≡k_3*x_2+b_3≡k_3*(k_1*k_2*x_t+b_1*k_2+b_2)+b_3≡k_1*k_2*k_3*x_t+b_1*k_2*k_3+b_2*k_3+b_3(operatorname{mod} 10007)\……\x_t≡k_t*x_{t-1}+b_t≡(prod_{i=1}^t k_i)+sum_{i=1}^t(b_i*prod_{j=i+1}^t k_j)(operatorname{mod} 10007)(数学归纳法)end{cases}
这样,只要我们求出xtx_t,那么整个环及连进来的点的值都可以求出.(由此看出,每个点都要保存两个系数k,bk,b)

关于求xt(以下简写为x)x_t(以下简写为x)的细节:设x≡kx+b(mod⁡10007)x≡kx+b(operatorname{mod} 10007)
若k=0,x=bk=0,x=b
若k=1k=1,当b=0b=0时有无穷组解;当b≠0时b e 0时,无解.
否则,(k−1)x≡−b(mod⁡10007)(k-1)x≡-b(operatorname{mod} 10007)
我们可以用两种方法:

  1. exgcd(k−1,10007,x,y)exgcd(k-1,10007,x,y)
  2. x=(pow(k−1,10005)∗(10007−b)mod⁡10007)x=(pow(k-1,10005)*(10007-b)operatorname{mod} 10007)(先求乘法逆元)
void exgcd(int a,int b,int &x,int &y)
{
	if(!b)x=1,y=0;
	else exgcd(b,a%b,y,x),y-=(a/b)*x;
}

因为边会变,所以可以想到用动态树.
但是有环要怎么处理呢,我们可以把一条边拆掉,并用splay节点中的一个变量sf(special  father)sf(special ~~ father)记录指向.(这条边的另一个点即为有向树的根)(详见代码中的dfs函数)
这样每个点ii都要维护两个系数k、bk、b,意义为:xi=k∗xroot.sf∗bx_i=k*x_{root.sf}*b.
在旋转等操作中需要维护这两个系数.

最后,提供一个小小的优化:先预处理出[0,10007)[0,10007)的乘法逆元(毕竟询问多)
设mod=10007mod=10007
如果用快速幂的话,预处理复杂度为O(mod∗logmod)O(mod*log_{mod}).
下面提供一个复杂度为O(mod)O(mod)的预处理方法:

inv[1]=1;
for(int i=2;i<mod;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;

为什么?证明:

设M=10007,t=⌊M/i⌋;k=Mmod⁡i; 设M=10007,t=leftlfloor{M/i} ight floor;k=M operatorname{mod} i;
t∗i+k≡0(mod⁡M)t*i+k≡0( operatorname{mod}M)
−t∗i≡k(mod⁡M)-t*i≡k( operatorname{mod}M)
−t∗inv[k]≡inv[i](mod⁡M)-t*inv[k]≡inv[i]( operatorname{mod}M)
inv[i]≡(M−⌊M/i⌋)∗inv[Mmod⁡i](mod⁡M)inv[i]≡(M-leftlfloor{M/i} ight floor)*inv[M operatorname{mod}i]( operatorname{mod}M)

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define g getchar()
#define lc tr[x].son[0]
#define rc tr[x].son[1]
using namespace std;
const int mod=10007,N=30010;
void qr(int &x)
{
	char c=g;bool v=x=0;
	while(!(isdigit(c)||c=='-'))c=g;
	if(c=='-')v=1,c=g;
	while(isdigit(c))x=x*10+c-'0',c=g;
	if(v)x=-x;
}
void write(int x)
{
	if(x/10)write(x/10);
	putchar(x%10+'0');
}
void pri(int x)
{
	if(x<0)putchar('-'),x=-x;
	write(x);puts("");
}
struct data//我们把环拆成树，去掉一条边（用sf记录这条删掉的边） 
{
	int k,b;
	data(){k=1;b=0;}
	data(int k,int b):k(k),b(b){}
	int sol(int x){return (k*x+b)%mod;}
	data operator +(const data a)
	{//每个点都用sf的x表出自己，由于sf是环中深度最大的点，所以把sf吊起，他就会自己表出自己，进而求出x，表出整个环的值 
		data c;
		c.k=k*a.k%mod;
		c.b=(a.k*b+a.b)%mod;
		return c;
	}//x1=k1*xt+b1,x2=k2*x1+b2=k2*(k1*xt+b1)+b2=k1*k2*xt+b1*k2+b2
}d[N],s[N];
struct node{int f,son[2],sf;}tr[N];
int inv[mod];//逆元 
bool v[N],in[N];//是否遍历过，是否入栈 
void dfs(int x)
{
	in[x]=v[x]=1;
	int f=tr[x].f;
	if(in[f])
	{
		tr[x].f=0;
		tr[x].sf=f;
	}
	if(!v[f])dfs(f);
	in[x]=0;
}
void update(int x){s[x]=s[lc]+d[x]+s[rc];}
bool rt(int x){return tr[tr[x].f].son[0]!=x&&tr[tr[x].f].son[1]!=x;}
void rotate(int x,int w)
{
	int f=tr[x].f,ff=tr[f].f,r,R;
	r=tr[x].son[w];R=f;tr[R].son[1-w]=r;if(r)tr[r].f=R;
	r=x;R=ff;if(tr[R].son[0]==f)tr[R].son[0]=r;else if(tr[R].son[1]==f)tr[R].son[1]=r;tr[r].f=R;
	r=f;R=x;tr[R].son[w]=r;tr[r].f=R;update(f);update(x);
}
void splay(int x)
{
	while(!rt(x))
	{
		int f=tr[x].f;
		if(rt(f))rotate(x,tr[f].son[0]==x);
		else 
		{
			int ff=tr[f].f,a=(tr[f].son[0]==x),b=(tr[ff].son[0]==f);
			rotate(a^b?x:f,a);rotate(x,b);
		}
	}
}
void access(int x){for(int y=0;x;x=tr[y=x].f)splay(x),rc=y,update(x);}
int find_root(int x)//不能makeroot，因为要保证sf为环中深度最大的点 
{
	access(x);splay(x);
	while(lc)x=lc;
	return x;
}
void link(int x,int y){access(x);splay(x);tr[x].f=y;}
void cut(int x)
{
	access(x);splay(x);
	tr[lc].f=0;lc=0;
	update(x);
}
int query(int x)
{
	access(x);splay(x);
	data s1=s[x];
	int tx=find_root(x),f=tr[tx].sf;
	access(f);splay(f);
	data s2=s[f];//x=kx+b
	if(!s2.k)return s1.sol(s2.b);//x=b 
	if(s2.k==1)return s2.b?-1:-2;//x=x+1(无解),x=x（无穷解）
	return s1.sol((mod-inv[s2.k-1])*s2.b%mod);
}
bool check(int x,int tx)//判断x是否在环上
{
	int y=tr[tx].sf;
	if(x==y)return 1;
	access(y);splay(y);splay(x); 
	return !rt(y);//如果y的位置变了，说明x在环上
}
void change(int x,int y,int k,int b)
{
	access(x);splay(x);d[x]=(data){k,b};update(x);
	int tx=find_root(x),ty;
	if(x==tx)
	{
		ty=find_root(y);
		if(ty==x)tr[x].sf=y;//x,y已经联通了，此时在加边就成环了 
		else tr[x].sf=0,link(x,y);//断开原来的树上没有的边，再连边。
	}
	else
	{
		//在环上
		if(check(x,tx))cut(x),link(tx,tr[tx].sf),tr[tx].sf=0;//环断成树了
		else  cut(x);//cut完，x已经成了深度最小的
		ty=find_root(y);
		if(ty==x)tr[x].sf=y; 
		else link(x,y);
	}
}
int main()
{
	int n;qr(n);
	inv[1]=1;
	for(int i=2;i<mod;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;/*
	t=M/i;k=M%i;
	t*i+k≡0(mod M)
	-t*i≡k(mod M)
	-t*inv[k]≡inv[i](mod M)
	inv[i]≡(M-M/i)*inv[M%i](mod M)
	*/
	for(int i=1;i<=n;i++)
	{
		int k,b;qr(k);qr(tr[i].f);qr(b);
		d[i]=s[i]=(data){k,b};
	}
	for(int i=1;i<=n;i++)if(!v[i])dfs(i);
	int m;qr(m);
	while(m--)
	{
		int x,k,b,f;
		char s[3];scanf("%s",s);qr(x);
		switch(s[0]){
			case 'A':pri(query(x));break;
			case 'C':qr(k);qr(f);qr(b);
					 change(x,f,k,b);break;
				}
	}
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zsyzlzy/p/12373891.html