Flandre Scarlet's Blog

颓不完作业来颓竞赛QAQ

BZOJ：3122-3124

校内：60+10+100（T1被map卡20分表示不服）

-=-=-=-=-=-=-=-=-=-=-=-鬼畜的分割线-=-=-=-=-=-=-=-=-=-=-=-

T1：给定a,b,x1,素数p

\[x_{i+1}=(ax_i+b) (mod~p)\]

求最小的n使得\(x_n=t\)

姿势：

若x1=t则n=1

若a=0则判断b是否等于t

若a=1

\[x_n=x_1+(n-1)b\]

这个显然用欧几里德扩展可以求解

若a>=2

\[x_n=a^{n-1}x_1+b \frac {a^{n-1}-1}{a-1}(mod~p)=t\]

\[设c为a-1的逆元\]

\[(x_1+bc)a^{n-1}=bc+t(mod~p)\]

欧几里德扩展解出\(a^{n-1}\)

最后用BSGS小姿势算一下n即可

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
LL p,a,b,x,t,T;
void E(LL a,LL b,LL &d,LL &x,LL &y)//ax+by=d
{
	if (b==0) d=a,x=1,y=0;
	else {E(b,a%b,d,x,y);T=x,x=y,y=T-a/b*y;return;}
}
int axbyc(LL a,LL b,LL c,LL &x,LL &y)
{
	LL X,Y,d,M;
	E(a,b,d,X,Y);
	if (c%d!=0) return 0;
	M=c/d;//aX+bY=d ==>aXM+bYM=c
	x=X*M;
	y=Y*M;
	return 1;
}
LL Pow(LL a,LL b,LL mod)
{
    a%=mod;LL ans=1;
    for(;b;b>>=1,a=a*a%mod)if (b&1) ans=ans*a%p;
    return ans;
}
struct _233
{
	LL a;int i;
}G[70000];
int l;
int cmp(const _233 &a,const _233 &b){return a.a<b.a;}
int l_b(int x,int n)
{
	int l=0,r=n-1,mid;
	while (l<=r)
	{
		mid=l+r>>1;
		if (G[mid].a==x)return G[mid].i;
		else if (G[mid].a<x)l=mid+1;
		else r=mid-1;
	}
	return -1;
}
LL GSBS(LL x,LL n,LL m)//x^y==n(mod m)
{
	x%=m;
	if (!x)if(!n)return 1;else return -1;
	l=0;
	int s=(int)sqrt((double)m)+1;
	LL cur=1,rec;
	for (int i=0;i<s;++i)
		G[l++]=(_233){cur,i},cur=cur*x%m;
	sort(G,G+l,cmp);
	LL mul=cur;cur=1;
	for (int i=0;i<s;++i)
	{
		LL more=(LL)n*Pow(cur,m-2,m)%m;
		if ((rec=l_b(more,l))!=-1)
			return i*s+rec;
		cur=cur*mul%m;
	}
	return -1;
}
LL c1()
{
	LL C=(t-x+p)%p,X,Y,t;
	E(b,p,t,X,Y);
	if (C%t) return -1;
	C/=t,X=X*C%p;
	if (X<0)X+=p;
	return X+1;
}
LL c2()
{
	LL c=Pow(a-1,p-2,p),A=(x+b*c)%p,C=(t+b*c)%p,X,Y;
	E(A,p,t,X,Y);
	if (C%t) return -1;C/=t;
	if (X<p) X=X%p+p;
	t=GSBS(a,X*C%p,p);
	if (t+1)return t+1;
	else return -1;
}
LL solve()
{
	if (x==t) return 1;
	if (a==0)
	{
		if (b==t) return 2;
		return -1;
	}
	if (a==1) return c1();
	else return c2();
}
int main()
{
	freopen("random9.in","r",stdin);
	freopen("random.out","w",stdout);
	int T;
	scanf ("%d",&T);
	while (T--)
	{
		scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x,&t);
		printf("%lld\n",solve());
	}
}

-=-=-=-=-=-=-=-=-=-=-=-稍鬼畜的分割线-=-=-=-=-=-=-=-=-=-=-=-

T2：给定森林，支持连接两个点和查询链上第K大

不会蛤蛤。

考场暴力，听说主席树+启发式合并+LCA

-=-=-=-=-=-=-=-=-=-=-=-略鬼畜的分割线-=-=-=-=-=-=-=-=-=-=-=-

T3：给定树，求直径（最长链）以及所有最长链共同经过的边数。

前一问取任一点DFS，找到最远点，再做一次DFS可破。

后一问先证明两个东西：直径必有交点；直径共同边（简称径链）是连续的。

然后维护某些乱七八糟的东西可破

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxm 400010
#define maxn 200010
using namespace std;
typedef long long LL;
struct Ed{int v;LL w;}E[maxm];
int n,idx[maxn],nxt[maxm],Si=0,U,V,W;
LL dis[maxn],mx[maxn],C[maxn],h[maxn],M;
void AE(int u,int v,LL w){E[Si]=(Ed){v,w};nxt[Si]=idx[u];idx[u]=Si++;}
void dfs(int u,int f)
{
	for (int i=idx[u];i+1;i=nxt[i])
		if (E[i].v!=f) dis[E[i].v]=dis[u]+E[i].w,h[E[i].v]=h[u]+1,dfs(E[i].v,u);
}
LL dfs2(int u,int f)
{
	LL tmp;mx[u]=dis[u];C[u]=0;
	for (int i=idx[u];i+1;i=nxt[i])
		if (E[i].v!=f) 
		{
			dis[E[i].v]=dis[u]+E[i].w;
			h[E[i].v]=h[u]+1;
			if (dis[E[i].v]>M) M=dis[E[i].v];
			tmp=dfs2(E[i].v,u);
			if (mx[u]==tmp) C[u]++;
			if (mx[u]<tmp) mx[u]=tmp,C[u]=1;
		}
	if (mx[u]==M&&f!=0&&C[u]!=1) W=u;
	return mx[u];
}
int main()
{
	memset(idx,-1,sizeof(idx));
	scanf("%d",&n);
	for (int i=1,u,v,w;i<n;i++)scanf("%d%d%d",&u,&v,&w),AE(u,v,w),AE(v,u,w);
	int l=1,r=1;
	dis[0]=0;dis[1]=0;
	dfs(1,0);
	for (int i=2;i<=n;i++)if (dis[i]>dis[l])l=i;//端l 
	dis[l]=0;dfs2(l,0);U=W;
	for (int i=2;i<=n;i++)if (dis[i]>dis[r])r=i;//端r 
	dis[r]=0;dfs2(r,0);V=W;
	h[U]=0;dis[U]=0;dfs(U,0);
	printf("%lld\n%lld\n",M,h[V]);
	return 0;
}

滚粗辣