Lvat_s Blog

考的实在是不尽人意。而且由于坑爹的学校杀，所以我应该是不会再去搞OI了。

坑应该也不会去填了。

感谢ygp老师和众多陪伴过我的人。

OI再见。

明显是一个最大流啊……

坑明天填上……

今天是2016年7月31日，我仍然没有填这个坑。

所以，我力争在三天内填好所有的坑(flag)，谢谢各位看我博客的神犇……

长期未填坑表示抱歉……

----------------

说好的填坑来了

我一开始以为是曼哈顿距离，错了好久……

拆点，两点间流量为两点间高度，然后考虑建超级源点连向每个有蜥蜴的柱子上面容量1

所有能跳出的柱子下面向超级汇点连接容量INF

没了

为什么？把蜥蜴看成1的流量模拟一下即可

下面程序中bfs_add为曼哈顿距离的建图

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=1005,INF=2100000000;

int r,c,d,h[N],en,level[N],S,T,cur[N],t[25][25],rex,p[N][N];
char mp[N][N];
queue<int> Q;
queue<pair<pair<int,int>,int> > Qx;

struct Edge{
int b,f,next,back;
}e[N*100];

inline int GetID(int x,int y){return (x-1)*c+y;}

inline void AddEdge(int sa,int sb,int sc){
//printf("Line %d %d %d\n",sa,sb,sc);
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

inline int bfs(){
memset(level,0,sizeof(level));
Q.push(S);level[S]=1;
while(!Q.empty()){
	int u=Q.front();Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(e[i].f && !level[v])level[v]=level[u]+1,Q.push(v);
	}
}
return level[T];
}

int dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int fl,v=e[i].b;
	if(level[v]==level[u]+1 && e[i].f && (fl=dfs(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		f-=fl;
		if(!f)return flow;
	}
}
return flow-f;
}

inline int Dinic(){
int ans=0;
while(bfs()){
	for(int i=1;i<=T;i++)cur[i]=h[i];
	ans+=dfs(S,INF);
}
return ans;
}

inline int Abs(const int &x){return x>0?x:-x;}
inline int Dist(const int &x1,const int &y1,const int &x2,const int &y2){return Abs(x2-x1)+Abs(y2-y1);}

/*inline void bfs_add(const int &x,const int &y){
int id=GetID(x,y);
memset(t,0,sizeof(t));
t[x][y]=1;
Qx.push(make_pair(make_pair(x+1,y),d-1));
Qx.push(make_pair(make_pair(x,y+1),d-1));
Qx.push(make_pair(make_pair(x-1,y),d-1));
Qx.push(make_pair(make_pair(x,y-1),d-1));
while(!Qx.empty()){
	pair<pair<int,int>,int> Px=Qx.front();Qx.pop();
	if(Px.first.first<1 || Px.first.first>r || Px.first.second<1 || Px.first.second>c)Px.first.first=0,Px.first.second=0;
	if(t[Px.first.first][Px.first.second])continue;
	t[Px.first.first][Px.first.second]=1;
	//printf("T:%d %d\n",Px.first.first,Px.first.second);
	if(Px.first.first==0 && Px.first.second==0){AddEdge(id+r*c,T,INF);continue;}
	if(p[Px.first.first][Px.first.second])AddEdge(id+r*c,GetID(Px.first.first,Px.first.second),INF);
	if(Px.second==0)continue;
    Qx.push(make_pair(make_pair(Px.first.first+1,Px.first.second),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first,Px.first.second+1),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first-1,Px.first.second),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first,Px.first.second-1),Px.second-1));
}
}*/

inline void Build(){
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(!p[i][j])continue;
		if(i-d<1 || i+d>r || j-d<1 || j+d>c)AddEdge(GetID(i,j)+r*c,T,INF);
		for(int i1=1;i1<=r;i1++){
			for(int j1=1;j1<=c;j1++){
				if(!p[i1][j1] || (i==i1 && j==j1))continue;
				if((i1-i)*(i1-i)+(j1-j)*(j1-j)<=d*d)AddEdge(GetID(i,j)+r*c,GetID(i1,j1),INF);
			}
		}
	}
}
}

int main(){
freopen("1066.in","r",stdin);
freopen("1066.out","w",stdout);
scanf("%d %d %d",&r,&c,&d);
S=2*r*c+1;T=S+1;
for(int i=1;i<=r;i++)scanf("%s",mp[i]+1);
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++)if(mp[i][j]>'0')p[i][j]=1;
}
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(p[i][j]){
			int id=GetID(i,j);
			AddEdge(id,r*c+id,mp[i][j]-'0');
			//bfs_add(i,j);
		}
	}
}
Build();
//printf("S:%d T:%d\n",S,T);
for(int i=1;i<=r;i++)scanf("%s",mp[i]+1);
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(mp[i][j]=='L')AddEdge(S,GetID(i,j),1),rex++;
	}
}
printf("%d\n",rex-Dinic());
return 0;
}

这是一个坑……晚上理解了Splay然后写出来再填坑吧……(那你为什么要开坑？怕忘了这件事啊……)

暂时无法理解splay……先放着吧过一阵子再填坑

突然觉得应该攒一些模版了……这样以后就可以方便的抄了

#include<cstdio>
#include<algorithm>
using namespace std;

int en,pre[30005],segn,n,q,top[30005],id[30005],data[30005],fa[30005],son[30005],siz[30005],dep[30005],h[30005];
char ask[10];

struct Edge{
int b,next;
}e[60005];

struct SegTree{
int l,r,v,sum;
}tree[120005];

void add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].v=data[pre[l]];
    tree[root].sum=data[pre[l]];
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tree[root].v=max(tree[root*2].v,tree[root*2+1].v);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

void Update(int root,int pos,int val){
if(tree[root].l==tree[root].r){
    tree[root].v+=val;
    tree[root].sum+=val;
    return;
}
int mid=(tree[root].l+tree[root].r)/2;
if(pos<=mid)Update(root*2,pos,val);
if(pos>mid)Update(root*2+1,pos,val);
tree[root].v=max(tree[root*2].v,tree[root*2+1].v);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

int QueryMax(int root,int l,int r){
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].v;
}
int mid=(tree[root].l+tree[root].r)/2,ans=-2147483647;
if(l<=mid)ans=max(ans,QueryMax(root*2,l,r));
if(r>mid)ans=max(ans,QueryMax(root*2+1,l,r));
return ans;
}

int QuerySum(int root,int l,int r){
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].sum;
}
int mid=(tree[root].l+tree[root].r)/2,ans=0;
if(l<=mid)ans+=QuerySum(root*2,l,r);
if(r>mid)ans+=QuerySum(root*2+1,l,r);
return ans;
}

void dfs1(int u,int father,int deep){
fa[u]=father;
dep[u]=deep;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}

void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=son[u] && v!=fa[u]){dfs2(v,v);}
}
}

int AskMax(int u,int v){
int f1=top[u],f2=top[v],ans=-2147483647;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(u,v);
        swap(f1,f2);
    }
    ans=max(ans,QueryMax(1,id[f1],id[u]));
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans=max(ans,QueryMax(1,id[u],id[v]));
return ans;
}

int AskSum(int u,int v){
int f1=top[u],f2=top[v],ans=0;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(u,v);
        swap(f1,f2);
    }
    ans+=QuerySum(1,id[f1],id[u]);
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans+=QuerySum(1,id[u],id[v]);
return ans;
}

int main(){
freopen("1036.in","r",stdin);
freopen("1036.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    add(sa,sb);
    add(sb,sa);
}
for(int i=1;i<=n;i++){
    scanf("%d",&data[i]);
}
dfs1(1,0,1);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&q);
while(q--){
    int sa,sb;
    scanf("%s %d %d",ask,&sa,&sb);
    if(ask[0]=='C'){Update(1,id[sa],sb-data[sa]);data[sa]=sb;}
    if(ask[1]=='M'){printf("%d\n",AskMax(sa,sb));}
    if(ask[1]=='S'){printf("%d\n",AskSum(sa,sb));}
}
return 0;
}

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct AC_Trie{
int fail,next[26],key;
AC_Trie(){fail=0;key=0;}
}tree[500005];

int n,cnt=1;
char s[1000005];
queue<int> Q;

void Ins(){
int len=strlen(s),j=1;
for(int i=0;i<len;i++){
	int p=s[i]-'a';
	if(tree[j].next[p]==0)tree[j].next[p]=++cnt;
	j=tree[j].next[p];
}
tree[j].key++;
}

void BFS(){
Q.push(1);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=0;i<=25;i++){
        int v=tree[u].next[i];
		if(v==0)continue;
		Q.push(v);
		if(u==1){
			tree[v].fail=1;
			continue;
		}
		int p=tree[u].fail;
		while(p){
			if(tree[p].next[i]){
				tree[v].fail=tree[p].next[i];
				break;
			}
			p=tree[p].fail;
		}
		if(!p)tree[v].fail=1;
	}
}
}

int GetAns(){
int len=strlen(s),ans=0,j=1;
for(int i=0;i<len;i++){
	int p=s[i]-'a';
	while(tree[j].next[p]==0 && j!=1)j=tree[j].fail;
	j=tree[j].next[p];
	if(j==0)j=1;
	int q=j;
	while(q!=1 && tree[q].key!=-1){
		ans+=tree[q].key;
		tree[q].key=-1;
		q=tree[q].fail;
	}
}
return ans;
}

int main(){
freopen("2222.in","r",stdin);
freopen("2222.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	scanf("%s",s);
	Ins();
}
BFS();
scanf("%s",s);
printf("%d\n",GetAns());
return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000005],m;

struct Node{
int v,mx,sum,lx,rx,siz,tag,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;

Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=sum=mx=val;
tag=rev=0;
siz=1;
if(v>=0)lx=rx=v;
else lx=rx=0;
}

void Node::Pushdown(){
if(tag){
	tag=rev=0;
	if(ch[0]!=Null){ch[0]->tag=1;ch[0]->sum=ch[0]->siz*v;ch[0]->v=v;}
	if(ch[1]!=Null){ch[1]->tag=1;ch[1]->sum=ch[1]->siz*v;ch[1]->v=v;}
	if(v>=0){
        if(ch[0]!=Null){ch[0]->lx=ch[0]->mx=ch[0]->rx=v*ch[0]->siz;}
        if(ch[1]!=Null){ch[1]->lx=ch[1]->mx=ch[1]->rx=v*ch[1]->siz;}
	}
	else {
		if(ch[0]!=Null){ch[0]->mx=v;ch[0]->lx=ch[0]->rx=0;}
        if(ch[1]!=Null){ch[1]->mx=v;ch[1]->lx=ch[1]->rx=0;}
	}
}
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
	swap(ch[0]->lx,ch[0]->rx);
	swap(ch[1]->lx,ch[1]->rx);
}
}

void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
sum=ch[0]->sum+ch[1]->sum+v;
mx=max(ch[0]->mx,ch[1]->mx);
mx=max(mx,ch[0]->rx+v+ch[1]->lx);
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place)Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
if(place==Null)root=x;
}

Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}

Node *Split(int pos,int tot){
Node *x=Find(root,pos);
Splay(x,Null);
Node *y=Find(root,pos+tot+1);
Splay(y,root);
return y->ch[0];
}

Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}

void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p;
p->mx=p->v=-1000000000;
p->rev=p->tag=p->siz=p->sum=p->lx=p->rx=0;
return p;
}

void Build_First(){
Null=GetNull();
a[1]=-1000000000;
a[n+2]=-1000000000;
root=Build(1,n+2);
}

void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}

void Delete(int pos,int val){
Node *seq=Split(pos,val),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}

void MakeSame(int pos,int tot,int val){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->tag=1;
seq->sum=seq->siz*val;
seq->v=val;
if(val>=0)seq->lx=seq->rx=seq->mx=seq->siz*val;
else seq->lx=seq->rx=0,seq->mx=val;
fat->Pushup();
fat->fa->Pushup();
}

void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
if(!seq->tag){
	seq->rev^=1;
	swap(seq->ch[0],seq->ch[1]);
	swap(seq->lx,seq->rx);
	fat->Pushup();
	fat->fa->Pushup();
}
}

int GetSum(int pos,int tot){
Node *seq=Split(pos,tot);
return seq->sum;
}

int main(){
freopen("1500.in","r",stdin);
freopen("1500.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);
Build_First();
for(int i=1;i<=m;i++){
	char s[10];
    scanf("%s",s);
    if(s[0]=='I'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		for(int i=1;i<=tot;i++)scanf("%d",&a[i]);
		Insert(pos,tot);
	}
	if(s[0]=='D'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Delete(pos,tot);
	}
	if(s[0]=='M' && s[2]=='K'){
		int pos,tot,val;
		scanf("%d %d %d",&pos,&tot,&val);
        MakeSame(pos,tot,val);
	}
	if(s[0]=='M' && s[2]=='X'){
		printf("%d\n",root->mx);
	}
	if(s[0]=='R'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Reverse(pos,tot);
	}
	if(s[0]=='G'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		printf("%d\n",GetSum(pos,tot));
	}
}
return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char s[500005];
int n,rank[500005],rank2[500005],height[500005],sa[500005],rmq[500005][20],ws[500005],wv[500005],er[20],log2[500005];

int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j*=2,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wv[i]=x[y[i]]]++;
	for(i=1;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
	for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void CalHeight(char *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}

void RMQ(){
int i,j;
er[0]=1;
for(i=1;i<20;i++)er[i]=er[i-1]<<1;
log2[0]=-1;
for(i=1;i<=n;i++)log2[i]=(i&(i-1))?log2[i-1]:log2[i-1]+1;
for(i=1;i<=n;i++)rmq[i][0]=height[i];
for(j=1;j<20;j++)for(i=1;i+er[j-1]-1<=n;i++)rmq[i][j]=min(rmq[i][j-1],rmq[i+er[j-1]][j-1]);
}

int LCP(int a,int b){
int x=rank[a],y=rank[b],t;
if(x>y)t=x,x=y,y=t;
x++;
int k=log2[y-x+1];
return min(rmq[x][k],rmq[y-er[k]+1][k]);
}

int main(){
freopen("suffix.in","r",stdin);
freopen("suffix.out","w",stdout);
scanf("%s",s);
n=strlen(s);
s[n]=0;
GetSA(s,sa,n+1,128);
CalHeight(s,sa,n);
RMQ();
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    printf("%d\n",LCP(sa,sb));
}
return 0;
}

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;

const double Pi=2*asin(1);
const int NUM_SIZE=100005;

int An,Bn,Cn,Rev[NUM_SIZE*3],Step,n;

struct Complex{
double a,b;
Complex(double as=0.0,double bs=0.0){a=as;b=bs;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
friend Complex operator/(Complex a,Complex b){return Complex((a.a*b.a+a.b*b.b)/(b.a*b.a+b.b*b.b),(b.a*a.b-a.a*b.b)/(b.a*b.a+b.b*b.b));}
double Mod(){return sqrt(a*a+b*b);}
}A[NUM_SIZE*3],B[NUM_SIZE*3],C[NUM_SIZE*3];

template<typename T>void Read(T &x){
int flag=1;
char ch;
while((ch=getchar())<'0' || ch>'9')if(ch=='-')flag=-1;
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
x*=flag;
}

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
		for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
		}
    }
}
if(flag==-1){for(int i=0;i<n;i++)x[i].a/=n;}
}

int main(){
freopen("34.in","r",stdin);
freopen("34.out","w",stdout);
Read(An);Read(Bn);
An++;Bn++;
Cn=An+Bn-1;
for(int i=0;i<An;i++)Read(A[i].a);
for(int i=0;i<Bn;i++)Read(B[i].a);
for(n=1,Step=0;n<Cn;Step++,n<<=1);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)printf("%d ",(int)(C[i].a+0.5));
putchar('\n');
return 0;
}

今天现学了置换群……知道了Burnside引理……（还在最初级的阶段啊）

Burnside引理：给一些置换，本质不同的染色方案数等于每种置换的不变元素的个数的平均数。

然后自然就是代码了。（我写了两种方法求逆元）

#include<cstdio>
#include<cstring>

int Sr,Sg,Sb,n,m,p,a[65][65],f[65][65][65],ans,b[65],d[65];

void Read(int &x){
char c;
while((c=getchar())<'0' || c>'9');
x=c-'0';
while((c=getchar())>='0' && c<='9'){
    x=x*10+c-'0';
}
}

int QuickPow(int a,int b){
int base=a,ans=1;
while(b){
    if(b%2)ans=(ans*base)%p;
    base=(base*base)%p;
    b/=2;
}
return ans;
}

void exgcd(int a,int b,int &x,int &y){
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,x,y);
int tp=x;
x=y;
y=tp-a/b*y;
}

int DP(int x){
memset(b,0,sizeof(b));
int Sum=0,last=0;
for(int i=1;i<=n;i++){
    if(!b[i]){
        b[i]=1;
        d[++Sum]=1;
        last=i;
        while(!b[a[x][last]]){
            d[Sum]++;
            b[a[x][last]]=1;
            last=a[x][last];
        }
    }
}
memset(f,0,sizeof(f));
f[0][0][0]=1;
for(int i=1;i<=Sum;i++){
    for(int j=Sr;j>=0;j--){
        for(int k=Sg;k>=0;k--){
            for(int l=Sb;l>=0;l--){
                if(j>=d[i]){f[j][k][l]=(f[j][k][l]+f[j-d[i]][k][l])%p;}
                if(k>=d[i]){f[j][k][l]=(f[j][k][l]+f[j][k-d[i]][l])%p;}
                if(l>=d[i]){f[j][k][l]=(f[j][k][l]+f[j][k][l-d[i]])%p;}
            }
        }
    }
}
return f[Sr][Sg][Sb];
}

int main(){
freopen("1004.in","r",stdin);
freopen("1004.out","w",stdout);
Read(Sr);Read(Sb);Read(Sg);Read(m);Read(p);
n=Sr+Sg+Sb;
for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        Read(a[i][j]);
    }
}
m++;
for(int i=1;i<=n;i++)a[m][i]=i;
for(int i=1;i<=m;i++){
    ans=(ans+DP(i))%p;
}
ans=(ans*QuickPow(m,p-2))%p;
printf("%d\n",ans);
return 0;
}

这是一个坑……得过一阵子再填……

NOIP爆炸了心情不好……

现在打算填坑了。

这题是一个树链剖分，据说LCT也行。但是蒟蒻我啥也不会，于是强行学了一个晚上的树链剖分，总算A掉了这题。

我觉得网上题解已经烂大街了……所以就不发题解了，只（懒）放（癌）代（发）码（作）。

树链剖分+线段树

#include<cstdio>
#include<algorithm>
using namespace std;

int n,w[30005],dep[30005],h[30005],en,data[30005],Q,id[30005],siz[30005],fa[30005],son[30005],top[30005],pre[30005],segn;
char ask[10];

struct Edge{
int b,next;
}e[60005];

struct SegTree{
int l,r,v,sum;
}tr[120005];

void add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void dfs1(int u,int father,int deep){
dep[u]=deep;
fa[u]=father;
son[u]=0;
siz[u]=1;
//printf("ZZT:%d %d %d\n",u,father,deep);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}

void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
//printf("Tr:%d %d\n",u,ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u] || v==son[u])continue;
    dfs2(v,v);
}
}

void Build(int root,int l,int r){
tr[root].l=l;
tr[root].r=r;
if(l==r){
    tr[root].v=data[pre[l]];
    tr[root].sum=data[pre[l]];
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tr[root].v=max(tr[root*2].v,tr[root*2+1].v);
tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
}

void Update(int root,int pos,int val){
if(tr[root].l==tr[root].r){
    tr[root].v+=val;
    tr[root].sum+=val;
    //printf("Tx:%d %d %d\n",root,tr[root].v,tr[root].sum);
    return;
}
int mid=(tr[root].l+tr[root].r)/2;
if(pos<=mid)Update(root*2,pos,val);
if(pos>=mid+1)Update(root*2+1,pos,val);
tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
tr[root].v=max(tr[root*2].v,tr[root*2+1].v);
}

int QuerySum(int root,int l,int r){
if(tr[root].l>=l && tr[root].r<=r){
    return tr[root].sum;
}
int mid=(tr[root].l+tr[root].r)/2;
int ans=0;
if(l<=mid)ans+=QuerySum(root*2,l,r);
if(r>=mid+1)ans+=QuerySum(root*2+1,l,r);
return ans;
}

int QueryMax(int root,int l,int r){
if(tr[root].l>=l && tr[root].r<=r){
    return tr[root].v;
}
int mid=(tr[root].l+tr[root].r)/2;
int ans=-2147483647;
if(l<=mid)ans=max(ans,QueryMax(root*2,l,r));
if(r>=mid+1)ans=max(ans,QueryMax(root*2+1,l,r));
return ans;
}

int AskSum(int u,int v){
int f1=top[u],f2=top[v],ans=0;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(f1,f2);
        swap(u,v);
    }
    ans+=QuerySum(1,id[f1],id[u]);
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans+=QuerySum(1,id[u],id[v]);
return ans;
}

int AskMax(int u,int v){
int f1=top[u],f2=top[v],ans=-2147483647;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(f1,f2);
        swap(u,v);
    }
    ans=max(ans,QueryMax(1,id[f1],id[u]));
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans=max(ans,QueryMax(1,id[u],id[v]));
return ans;
}

int main(){
freopen("1036.in","r",stdin);
freopen("1036.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    add(sa,sb);
    add(sb,sa);
}
for(int i=1;i<=n;i++){
    scanf("%d",&data[i]);
}
dfs1(1,0,1);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&Q);
while(Q--){
    int sa,sb;
    scanf("%s %d %d",&ask,&sa,&sb);
    if(ask[0]=='C'){
        Update(1,id[sa],sb-data[sa]);
        data[sa]=sb;
    }
    if(ask[0]=='Q'){
        if(ask[1]=='S'){
            printf("%d\n",AskSum(sa,sb));
        }
        if(ask[1]=='M'){
            printf("%d\n",AskMax(sa,sb));
        }
    }
}
return 0;
}

树链剖分+树状数组（正在填坑中……）

LCT（正在填坑中……）