T1
暴力写挂.jpg
正解考虑枚举有几个小塔放了奇数个，然后剩下的就变成球和盒子的问题，统一算
orz wxx，tql
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1000005; 6 int fac[N],inv[N]; 7 long long T,n,m,k,mod; 8 int Qpow(int x,int k) 9 { 10 if(k<=1) return k?x:1; 11 int tmp=Qpow(x,k>>1); 12 return 1ll*tmp*tmp%mod*((k&1)?x:1)%mod; 13 } 14 void Pre() 15 { 16 fac[0]=inv[0]=1; 17 for(int i=1;i<mod;i++) fac[i]=1ll*fac[i-1]*i%mod; 18 inv[mod-1]=Qpow(fac[mod-1],mod-2); 19 for(int i=mod-2;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; 20 } 21 int C(int a,int b) 22 { 23 if(a<b||a<0||b<0) return 0; 24 return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod; 25 } 26 int Lucas(long long a,long long b) 27 { 28 return b?1ll*C(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod:1; 29 } 30 int main() 31 { 32 scanf("%lld",&T); 33 while(T--){ 34 scanf("%lld%lld%lld%lld",&n,&m,&k,&mod),Pre(); 35 if(!n&&!m) puts("0"); 36 else if(!n) printf("%d ",(k&1)?0:Lucas((k>>1)+m-1,m-1)); 37 else if(!m) printf("%d ",Lucas(k+n-1,n-1)); 38 else 39 { 40 int ans=0; 41 for(int i=0;i<=n;i++) 42 if(((k-i)&1)==0) 43 (ans+=1ll*Lucas(n,i)*Lucas(((k-i)>>1)+n+m-1,n+m-1)%mod)%=mod; 44 printf("%d ",ans); 45 } 46 } 47 return 0; 48 }
T2
效率垫底.jpg
用DFS序转成二维数点，然后做就完了
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=100005,M=200005,K=19; 6 int n,m,q,op,t1,t2,id,cnt,tot,num; 7 int p[N],noww[M],goal[M],upp[N][K],ans[N]; 8 int siz[N],anc[N],dep[N],imp[N],dfn[N],top[N]; 9 int root[N],val[N*330],lson[N*330],rson[N*330]; 10 void Link(int f,int t) 11 { 12 noww[++cnt]=p[f]; 13 goal[cnt]=t,p[f]=cnt; 14 noww[++cnt]=p[t]; 15 goal[cnt]=f,p[t]=cnt; 16 } 17 void DFS(int nde,int fth,int dth) 18 { 19 int tmp=0; 20 siz[nde]=1,anc[nde]=fth,dep[nde]=dth; 21 for(int i=p[nde],g;i;i=noww[i]) 22 if((g=goal[i])!=fth) 23 { 24 DFS(g,nde,dth+1),siz[nde]+=siz[g]; 25 if(siz[g]>tmp) tmp=siz[g],imp[nde]=g; 26 } 27 } 28 void Decompose(int nde,int upt) 29 { 30 dfn[nde]=++tot,top[nde]=upt; 31 if(imp[nde]) 32 { 33 Decompose(imp[nde],upt); 34 for(int i=p[nde],g;i;i=noww[i]) 35 if((g=goal[i])!=imp[nde]&&g!=anc[nde]) Decompose(g,g); 36 } 37 } 38 int LCA(int x,int y) 39 { 40 while(top[x]!=top[y]) 41 { 42 if(dep[top[x]]<dep[top[y]]) 43 swap(x,y); x=anc[top[x]]; 44 } 45 return dep[x]<dep[y]?x:y; 46 } 47 void Pre() 48 { 49 for(int i=1;i<=n;i++) upp[i][0]=anc[i]; 50 for(int i=1;i<=18;i++) 51 for(int j=1;j<=n;j++) 52 upp[j][i]=upp[upp[j][i-1]][i-1]; 53 } 54 void Add(int &nde,int l,int r,int pos,int tsk) 55 { 56 if(!nde) nde=++id; 57 if(l==r) val[nde]+=tsk; 58 else 59 { 60 int mid=(l+r)>>1; 61 if(pos<=mid) Add(lson[nde],l,mid,pos,tsk); 62 else Add(rson[nde],mid+1,r,pos,tsk); 63 val[nde]=val[lson[nde]]+val[rson[nde]]; 64 } 65 } 66 void Modify(int pos,int pot,int tsk) 67 { 68 for(int i=pos;i<=n;i+=i&-i) 69 Add(root[i],1,n,pot,tsk); 70 } 71 int Query(int &nde,int l,int r,int ll,int rr) 72 { 73 if(!nde) nde=++id; 74 if(ll>rr) return 0; 75 if(l>=ll&&r<=rr) return val[nde]; 76 else 77 { 78 int mid=(l+r)>>1,ret=0; 79 if(mid>=ll) ret+=Query(lson[nde],l,mid,ll,rr); 80 if(mid<rr) ret+=Query(rson[nde],mid+1,r,ll,rr); 81 return ret; 82 } 83 } 84 int Count(int xa,int ya,int xb,int yb) 85 { 86 int ret1=0,ret2=0; 87 for(int i=xa-1;i;i-=i&-i) 88 ret1+=Query(root[i],1,n,1,yb)-Query(root[i],1,n,1,ya-1); 89 for(int i=xb;i;i-=i&-i) 90 ret2+=Query(root[i],1,n,1,yb)-Query(root[i],1,n,1,ya-1); 91 return ret2-ret1; 92 } 93 int main() 94 { 95 scanf("%d",&n); 96 for(int i=1;i<n;i++) 97 scanf("%d%d",&t1,&t2),Link(t1,t2); 98 DFS(1,0,1),Decompose(1,1),Pre(); 99 scanf("%d",&m); 100 for(int i=1;i<=m;i++) 101 { 102 scanf("%d%d",&t1,&t2); 103 Modify(dfn[t1],dfn[t2],1); 104 Modify(dfn[t2],dfn[t1],1); 105 } 106 scanf("%d",&q); 107 while(q--) 108 { 109 scanf("%d%d%d",&op,&t1,&t2); 110 if(op==1) Modify(dfn[t1],dfn[t2],1),Modify(dfn[t2],dfn[t1],1); 111 else if(op==2) Modify(dfn[t1],dfn[t2],-1),Modify(dfn[t2],dfn[t1],-1); 112 else 113 { 114 int lca=LCA(t1,t2); 115 if(lca==t1) 116 { 117 int ly=dfn[t2],ry=dfn[t2]+siz[t2]-1,nde=t2; 118 for(int i=18;~i;i--) 119 if(dep[upp[nde][i]]>dep[t1]) nde=upp[nde][i]; 120 int lx=dfn[nde],rx=dfn[nde]+siz[nde]-1; 121 ans[++num]=Count(1,ly,lx-1,ry)+Count(rx+1,ly,n,ry); 122 } 123 else if(lca==t2) 124 { 125 swap(t1,t2); 126 int ly=dfn[t2],ry=dfn[t2]+siz[t2]-1,nde=t2; 127 for(int i=18;~i;i--) 128 if(dep[upp[nde][i]]>dep[t1]) nde=upp[nde][i]; 129 int lx=dfn[nde],rx=dfn[nde]+siz[nde]-1; 130 ans[++num]=Count(1,ly,lx-1,ry)+Count(rx+1,ly,n,ry); 131 } 132 else 133 { 134 int lx=dfn[t1],rx=dfn[t1]+siz[t1]-1; 135 int ly=dfn[t2],ry=dfn[t2]+siz[t2]-1; 136 ans[++num]=Count(lx,ly,rx,ry); 137 } 138 } 139 } 140 for(int i=1;i<=num;i++) 141 { 142 printf("%d",ans[i]); 143 if(i!=num) puts(""); 144 } 145 return 0; 146 }
T3
