2
15
2016
1

【SDOI2013】校测

颓不完作业来颓竞赛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;
}

滚粗辣

 

Category: 魔泥赛 | Tags: | Read Count: 1000
AP 1st Inter Economi 说:
2022年9月08日 21:38

The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 1st Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com