Newnode

upd:

是时候记个游记了。。。

day0

打板

感觉3天后就要退役了。

asdfz（感觉像是键盘上随便敲的>_<）大军来碾压了= =

跪稳A队的wyy+lzz。

晚上被立flag：明天要稳>_<

Day1

T3：smg！为毛和我校内胡策题基本一样！30min= =

T1：smg！神题不会！咦？样例是smg！2^nk？证明了一下= =20min

T2：smg！神题不会！暴力吧！咦？数据辣么水？

爆零滚粗了。

祝cjy二试翻盘

---

Day2

T2：smg！神题不会！看起来= =50是km？忘了怎么办！我会费用流但好像会被卡？！不管了先写了再说= =30min later：贪心大法吼！我会线段树我自豪！

T1：smg！神题不会！期望题？期望的线性性大法吼！裸BIT= =省选画风不对！

这时候大概过了1h40min。。。颓废开始了。。。

T3：smg！计算几何大法吼！防AK神题！写了40分暴力。。。60太烦了还是颓吧。。。

结束了。。。跪cjyday2 260虐场。。。然而noip= =可怜的cjy= =

膜拜lzz、wyy、qns、hshA队

膜拜wlpB队

退役了真开心。。。

这个博客才开通= =

以后可能就不会怎么更了= =

也许会有点和oi无关的吧= =

goodbye My oi

goodbye My dream

goodbye My friends

其实我也进队的说= =

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=500005;

char s[N],str[N];

int p[N],n,m;

void Manacher()
{
	int Mx=0,pos=0;
	for(int i=1;i<=n;i++)
	{
		if(Mx>i)
			p[i]=min(p[2*pos-i],Mx-i);
		else
			p[i]=0;
		for(;str[i+p[i]]==str[i-p[i]];p[i]++);
		if(p[i]+i>Mx)
        	Mx=p[i]+i,
        	pos=i;
	}
}

int main()
{
	while(~scanf("%s",s+1))
	{
		m=strlen(s+1);
		str[0]='$';
		str[1]='#';
		for(int i=1;i<=m;i++)
			str[i*2]=s[i];
		for(int i=1;i<=m;i++)
			str[i*2+1]='#';
		n=m*2+1;
		Manacher();
		int Ans=0;
		for(int i=1;i<=n;i++)
			Ans=max(Ans,p[i]);
		printf("%d\n",Ans-1);
	}
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

#define Clear(_,__) memset(_,__,sizeof _)

typedef double DB;

const int N=505,M=20005,oo=1e9;

const DB eps=1e-8;

int e[M],next[M],G[N],Le[N],n,m,S,T,Sa,tot,A[N],B[N],Can[55][55];

DB f[M];

void adde(int u,int v,DB c)
{
	e[++tot]=v;f[tot]=c;next[tot]=G[u];G[u]=tot;
	e[++tot]=u;f[tot]=0;next[tot]=G[v];G[v]=tot;
}

bool bfs()
{
	queue<int> Q;
	Clear(Le,-1);
	Q.push(S);
	Le[S]=1;
	while(!Q.empty()&&Le[T]==-1)
	{
		int u=Q.front();
		Q.pop();
		for(int i=G[u];i;i=next[i])
		{
			int v=e[i];
			if(Le[v]==-1&&f[i]>eps)
				Q.push(v),
				Le[v]=Le[u]+1;
		}
	}
	return Le[T]!=-1;
}

DB dfs(int u,DB delta)
{
	if(u==T)
		return delta;
	DB w=0,t;
	for(int v,i=G[u];i&&w+eps<delta;i=next[i])
	{
		v=e[i];
		if(Le[v]==Le[u]+1&&f[i]>eps)
			t=dfs(v,min(delta-w,f[i])),
			w+=t,
			f[i]-=t,
			f[i^1]+=t;
	}
	if(w<eps)
		Le[u]=-1;
	return w;
}

DB Maxflow()
{
	DB Maxf=0;
	while(bfs())
		Maxf+=dfs(S,oo);
	return Maxf;
}

bool check(DB Mid)
{
	Clear(G,0);
	tot=1;
	for(int i=1;i<=n;i++)
		adde(i+m,T,A[i]);
	for(int i=1;i<=m;i++)
		adde(S,i,Mid*B[i]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			if(Can[i][j])
				adde(i,j+m,oo);
	return Maxflow()>=Sa;
}

int main()
{
	scanf("%d%d",&n,&m);
	S=0;
	T=n+m+1;
	for(int i=1;i<=n;i++)
		scanf("%d",&A[i]),
		Sa+=A[i];
	for(int i=1;i<=m;i++)
		scanf("%d",&B[i]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&Can[i][j]);
	DB l=0,r=5e6,Mid;
	while(l+1e-5<r)
		if(check(Mid=(l+r)/2))
			r=Mid;
		else
			l=Mid;
	printf("%.4lf\n",Mid);
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

typedef long long LL;

const int N=50005;

int d[N],p[N],f[N],s[N],mu[N],num[N],n,m,t,tot;

void Linear_Shaker(int n)
{
	d[1]=mu[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!f[i])
			p[++tot]=i,
			d[i]=2,
			mu[i]=-1,
			num[i]=2;
		for(int j=1;j<=tot&&p[j]*i<=n;j++)
		{
			int k=p[j]*i;
			f[k]=1;
			if(i%p[j]==0)
			{
				mu[k]=0;
				d[k]=d[i]/num[i]*(num[k]=num[i]+1);
				break;
			}
			mu[k]=-mu[i];
			d[k]=d[i]<<1;
			num[k]=2;
		}
	}
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+mu[i],
		d[i]+=d[i-1];
}

LL Ask(int n,int m)
{
	if(n>m)
		swap(n,m);
	LL Ans=0;
	for(int i=1,k;i<=n;i=k+1)
		k=min(n/(n/i),m/(m/i)),
		Ans+=(s[k]-s[i-1])*(LL)d[n/i]*d[m/i];
	return Ans;
}

int main()
{
	Linear_Shaker(N-5);
	scanf("%d",&t);
	while(t--)
		scanf("%d%d",&n,&m),
		printf("%lld\n",Ask(n,m));
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

typedef long long LL;

LL n,Ans;

LL gcd(LL a,LL b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}

LL Mul(LL a,LL b,LL p)
{
	LL k=a*b-(LL)((long double)a/p*b+1e-8)*p;
	return k<0?k+p:k;
}

LL Pow(LL a,LL b,LL p)
{
	LL k=1;
	while(b)
	{
		if(b&1)
			k=Mul(a,k,p);
		a=Mul(a,a,p);
		b>>=1;
	}
	return k;
}

bool check(LL k,LL r,LL s,LL n)
{
	LL w=Pow(k,r,n),p=w;
	for(int i=1;i<=s;i++)
	{
		w=Mul(w,w,n);
		if(w==1&&p!=n-1&&p!=1)
			return 0;
		p=w;
	}
	return w==1;
}

bool Miller_Rabin(LL n)
{
	if(n==2)
		return 1;
	if(!(n&1))
		return 0;
	LL r=n-1,s=0;
	while(!(r&1))
		r>>=1,
		s++;
	for(int i=1;i<=10;i++)
		if(!check(rand()%(n-1)+1,r,s,n))
			return 0;
	return 1;
}

LL rho(LL n,LL c)
{
	LL k=2,x=rand()%(n-1)+1,y=x,p=1;
	for(LL i=1;p==1;i++)
	{
		x=(Mul(x,x,n)+c)%n;
		p=gcd(n,y>x?y-x:x-y);
		if(i==k)
			y=x,
			k<<=1;
	}
	return p;
}

void Pollard_rho(LL n)
{
	if(n==1)
		return;
	if(Miller_Rabin(n))
	{
		Ans=max(Ans,n);
		return ;
	}
	LL t=n;
	while(t==n)
		t=rho(n,rand()%(n-1)+1);
	Pollard_rho(t);
	Pollard_rho(n/t);
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld",&n);
		Ans=0;
		Pollard_rho(n);
		if(Ans==n)
			puts("Prime");
		else
			printf("%lld\n",Ans);
	}
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=1200005;

int mask,n;

char s[3000005];

void fix(char *s,int mask)
{
	int len=strlen(s);
	for(int i=0;i<len;i++)
		mask=(mask*131+i)%len,
		swap(s[i],s[mask]);
}

namespace Lct
{
	int val[N],p[N],c[N][2],tag[N];
	
	#define Lc c[x][0]
	#define Rc c[x][1]
	
	bool is_root(int x)
	{
		return !p[x]||(c[p[x]][0]!=x&&c[p[x]][1]!=x);
	}
	
	void Add(int x,int k)
	{
		if(x)
			tag[x]+=k,
			val[x]+=k;
	}
	
	void push_down(int x)
	{
		if(tag[x])
			Add(Lc,tag[x]),
			Add(Rc,tag[x]),
			tag[x]=0;
	}
	
	void All_push_down(int x)
	{
		if(!is_root(x))
			All_push_down(p[x]);
		push_down(x);
	}
	
	void Rotate(int x)
	{
		int y=p[x],k=c[y][1]==x,ir=is_root(y);
		c[y][k]=c[x][!k];
		c[x][!k]=y;
		p[c[y][k]]=y;
		p[x]=p[y];
		p[y]=x;
		if(!ir)
			c[p[x]][c[p[x]][1]==y]=x;
	}
	
	void splay(int x)
	{
		All_push_down(x);
		while(!is_root(x))
			if(is_root(p[x]))
				Rotate(x);
			else if((c[p[p[x]]][1]==p[x])==(c[p[x]][1]==x))
				Rotate(p[x]),
				Rotate(x);
			else
				Rotate(x),
				Rotate(x);
	}
	
	int Access(int x)
	{
		int y=0;
		for(;x;x=p[x])
			splay(x),
			Rc=y,
			y=x;
		return y;
	}
	
	void link(int x,int y)
	{
		Access(y);
		splay(y);
		p[x]=y;
		Add(y,val[x]);
	}
	
	void cut(int x)
	{
		Access(x);
		splay(x);
		Add(Lc,-val[x]);
		p[Lc]=0;
		Lc=0;
	}
	
	#undef Lc
	#undef Rc
}

namespace Sam
{
	int Son[N][26],pre[N],Len[N],last=1,Now=1;
	
	void Extend(int x)
	{
		int p=last,np=++Now;
		Lct::val[np]=1;
		Len[np]=Len[p]+1;
		for(;p&&!Son[p][x];p=pre[p])
			Son[p][x]=np;
		if(!p)
			pre[np]=1,
			Lct::link(np,1);
		else
		{
			int q=Son[p][x];
			if(Len[q]==Len[p]+1)
				pre[np]=q,
				Lct::link(np,q);
			else
			{
				int nq=++Now;
				memcpy(Son[nq],Son[q],sizeof Son[q]);
				Len[nq]=Len[p]+1;
				pre[nq]=pre[q];
				Lct::link(nq,pre[nq]);
				pre[q]=nq;
				pre[np]=nq;
				Lct::cut(q);
				Lct::link(q,nq);
				Lct::link(np,nq);
				for(;p&&Son[p][x]==q;p=pre[p])
					Son[p][x]=nq;
			}
		}
		last=np;
	}
	
	void Build(char *s)
	{
		while(*s)
			Extend(*s-'A'),
			s++;
	}
	
	int Ask(char *s)
	{
		int p=1;
		for(;*s;s++)
			if(!(p=Son[p][*s-'A']))
				return 0;
		Lct::splay(p);
		return Lct::val[p];
	}
}

int main()
{
	scanf("%d%s",&n,s);
	Sam::Build(s);
	while(n--)
	{
		char op[10];
		scanf("%s",op);
		if(op[0]=='A')
			scanf("%s",s),
			fix(s,mask),
			Sam::Build(s);
		else
		{
			scanf("%s",s);
			fix(s,mask);
			int Ans=Sam::Ask(s);
			printf("%d\n",Ans);
			mask^=Ans;
		}
	}
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

typedef long long LL;

const int N=500005,Mod=998244353,G=3;

int X[N],Y[N],n,m,Rev[N],Len,Ny,g[50],Ng[50];

int Pow(int x,int y)
{
	int k=1;
	while(y)
	{
		if(y&1)
			k=k*(LL)x%Mod;
		x=(LL)x*x%Mod;
		y>>=1;
	}
	return k;
}

void Prepare(int& n)
{
	int Len=0;
	while((1<<++Len)<2*n);
	n=1<<Len;
	for(int i=1;i<n;i++)
		Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Len-1));
	for(int i=1;i<20;i++)
        g[i]=Pow(G,(Mod-1)>>i),
        Ng[i]=Pow(g[i],Mod-2);
    Ny=Pow(n,Mod-2);
}

int Add(int x,int y)
{
	x+=y;
	if(x>=Mod)
		x-=Mod;
	if(x<0)
		x+=Mod;
	return x;
}

void NTT(int F[],int n,int flag)
{
	for(int i=0;i<n;i++)
		if(i<Rev[i])
			swap(F[i],F[Rev[i]]);
	for(int i=1,k=1;i<n;i<<=1,k++)
	{
		int Wn=flag==1?g[k]:Ng[k];
		for(int j=0;j<n;j+=i<<1)
		{
			int W=1,x,y;
			for(int k=0;k<i;k++)
				x=F[j+k],
				y=F[j+k+i]*(LL)W%Mod,
				F[j+k]=Add(x,y),
				F[j+k+i]=Add(x,-y),
				W=W*(LL)Wn%Mod;
		}
 	}
 	if(flag==-1)
 		for(int i=0;i<n;i++)
 			F[i]=F[i]*(LL)Ny%Mod;
}

int main()
{
	scanf("%d%d",&n,&m);
	n++;
	m++;
	for(int i=0;i<n;i++)
		scanf("%d",&X[i]);
	for(int i=0;i<m;i++)
		scanf("%d",&Y[i]);
	Prepare(Len=max(n,m));
	NTT(X,Len,1);
	NTT(Y,Len,1);
	for(int i=0;i<Len;i++)
		X[i]=X[i]*(LL)Y[i]%Mod;
	NTT(X,Len,-1);
	for(int i=0;i<n+m-1;i++) printf("%d ",X[i]);
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=200005;

char s[N];

int a[N],b[N],t1[N],t2[N],c[N],sa[N],rk[N],h[N],n;

void get_SA(int m)
{
	int *x=t1,*y=t2;
	for(int i=1;i<=n;i++)
		c[x[i]=a[i]]++;
	for(int i=1;i<=m;i++)
		c[i]+=c[i-1];
	for(int i=n;i;i--)
		sa[c[x[i]]--]=i;
	for(int i=1;i<n&&(i==1||m<n);i<<=1,swap(x,y))
	{
		int p=0,j;
		for(j=n-i+1;j<=n;j++)
			y[++p]=j;
		for(j=1;j<=n;j++)
			if(sa[j]>i)
				y[++p]=sa[j]-i;
		for(j=1;j<=m;j++)
			c[j]=0;
		for(j=1;j<=n;j++)
			c[x[j]]++;
		for(j=1;j<=m;j++)
			c[j]+=c[j-1];
		for(j=n;j;j--)
			sa[c[x[y[j]]]--]=y[j];
		for(m=0,j=1;j<=n;j++)
			y[sa[j]]=m+=j==1||x[sa[j]]!=x[sa[j-1]]||x[sa[j]+i]!=x[sa[j-1]+i];
	}
}

void get_Height()
{
	for(int i=1;i<=n;i++)
		rk[sa[i]]=i;
	for(int i=1,k=0,j;i<=n;h[rk[i++]]=k)
		for(k?k--:0,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
}

int main()
{
	gets(s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		a[i]=s[i]-'a'+1;
	get_SA(26);
	get_Height();
	for(int i=1;i<=n;i++)
		printf("%d ",sa[i]);
	puts("");
	for(int i=2;i<=n;i++)
		printf("%d ",h[i]);
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

typedef double DB;
typedef long long LL;

const DB Pi=acos(-1.0);

const int N=500005;

struct Complex
{
	DB r,i;
	Complex(DB _=0,DB __=0):r(_),i(__){}
};

Complex operator+(const Complex& A,const Complex& B)
{
	return Complex(A.r+B.r,A.i+B.i);
}

Complex operator-(const Complex& A,const Complex& B)
{
	return Complex(A.r-B.r,A.i-B.i);
}

Complex operator*(const Complex& A,const Complex& B)
{
	return Complex(A.r*B.r-A.i*B.i,A.i*B.r+B.i*A.r);
}

Complex X[N],Y[N];

int n,m,Rev[N],Len,a[N],b[N];

void Prepare(int& n)
{
	int Len=0;
	while((1<<++Len)<2*n);
	n=1<<Len;
	for(int i=1;i<n;i++)
		Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Len-1));
}

void FFT(Complex F[],int n,int flag)
{
	for(int i=0;i<n;i++)
		if(i<Rev[i])
			swap(F[i],F[Rev[i]]);
	for(int i=1;i<n;i<<=1)
	{
		Complex Wn(cos(Pi/i),flag*sin(Pi/i));
		for(int j=0;j<n;j+=i<<1)
 		{
			Complex W(1,0),x,y;
			for(int k=0;k<i;k++)
				x=F[j+k],
				y=F[j+k+i]*W,
				F[j+k]=x+y,
				F[j+k+i]=x-y,
				W=W*Wn;
		}
 	}
 	if(flag==-1)
 		for(int i=0;i<n;i++)
 			F[i].r/=n;
}

int main()
{
	scanf("%d%d",&n,&m);
	n++;
	m++;
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]),
		X[i]=Complex(a[i],0);
	for(int i=0;i<m;i++)
		scanf("%d",&b[i]),
		Y[i]=Complex(b[i],0);
	Prepare(Len=max(n,m));
	FFT(X,Len,1);
	FFT(Y,Len,1);
	for(int i=0;i<Len;i++)
		X[i]=X[i]*Y[i];
	FFT(X,Len,-1);
	for(int i=0;i<n+m-1;i++) printf("%lld ",(LL)(X[i].r+0.5));
	return 0;
}

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=5005;

typedef double DB;

struct Point
{
	DB x,y;
	Point(DB _=0,DB __=0):x(_),y(__){}
}p[N],st[N];

Point operator-(const Point& a,const Point& b)
{
	return Point(a.x-b.x,a.y-b.y);
}

DB operator*(const Point& a,const Point& b)
{
	return a.x*b.y-a.y*b.x;
}

DB sqr(DB x)
{
	return x*x;
}

DB operator^(const Point& a,const Point& b)
{
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

bool operator<(const Point& a,const Point& b)
{
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

bool cmp(const Point& a,const Point& b)
{
	DB t=(a-p[1])*(b-p[1]);
	if(t==0)
		return (a^p[1])<(b^p[1]);
	return t>0;
}

int n,top;

void Graham()
{
	for(int i=1;i<=n;i++)
	{
		while(top>=2&&(p[i]-st[top-1])*(st[top]-st[top-1])>=0)
			top--;
		st[++top]=p[i]; 
	}
}

DB Get_Length()
{
	DB Ans=0;
	for(int i=1;i<top;i++)
		Ans+=st[i]^st[i+1];
	return Ans+(st[1]^st[top]);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	for(int i=2;i<=n;i++)
		if(p[i]<p[1])
			swap(p[i],p[1]);
	sort(p+2,p+n+1,cmp);
	Graham();
	printf("%.2lf",Get_Length());
	return 0;
}