A.普通计算姬
题意：给丁一棵树，每个点有一个权值，用sum(x)表示以x为根的子树的权值和，要求支持两种操作：
1 u v ：修改点u的权值为v。
2 l r : 求∑sum[i] l<=i<=r
n,m(操作数)<=10^5
题解:数据范围比较小，考虑分块重建的做法。
求出每个点的dfs序和子树的区间，这样就可以On建出所有节点的sum的前缀和。
然后每次修改操作都把操作存下来，每次查询先找出这段区间的和，再去操作里处理这些操作对这个查询的影响。
具体实现就是：把每个点的子树的dfs序范围的左右端点都扔到一棵主席树里面，每次查询一个区间时候，枚举修改操作，在主席树里面查询，修改操作修改的点影响的子树数量就=右端点大等于它的dfs序的数量-左端点大于它的dfs序的数量。
然后当操作达到一定数量的时候，暴力On重建一发。
如果操作达到k时候重建，那么复杂度就大概是n^2/k+nklogn,题目有4s，很科学。
然后这破题写了好久，还wa了好多次,代码丑。
#include<iostream> #include<cstdio> #include<cmath> #define ll unsigned long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } long long q[100005],q2[100005]; int top=0; long long b[100005]; ll sum[100005],num[100005]; int rt1[100005],rt2[100005]; int op,u,v,cnt=0,n,m,dn=0,cc=0,rt,head[100005]; struct edge{ int to,next; }e[200005]; int nl[100005],nr[100005]; ll ans=0; struct TREE{ int l,r,x; }T[10000005]; void ins(int f,int t) { e[++cnt].next=head[f];head[f]=cnt; e[cnt].to=t; } int query(int x,int ad) { // cout<<"query"<<x<<" "<<ad<<endl; if(ad>n||x==0) return 0; int l=1,r=n,sum=0; while(l<r&&x) { // cout<<l<<" "<<r<<" "<<x<<" "<<sum<<endl; int mid=(l+r)>>1; if(ad<=mid) {sum+=T[T[x].r].x;x=T[x].l;r=mid;} else {x=T[x].r;l=mid+1;} } //cout<<sum<<" "<<T[x].x<<endl; return sum+T[x].x; } void inst(int x,int ls,int ad) { // cout<<"inst"<<x<<" "<<ls<<" "<<ad<<endl; int l=1,r=n; while(l<r) { int mid=(l+r)>>1; if(ad<=mid) { T[x].l=++cc;T[x].r=T[ls].r;T[x].x=T[ls].x+1; r=mid;x=T[x].l;ls=T[ls].l; } else { T[x].r=++cc;T[x].l=T[ls].l;T[x].x=T[ls].x+1; l=mid+1;x=T[x].r;ls=T[ls].r; } // cout<<l<<" "<<r<<" "<<x<<" "<<ls<<endl; } T[x].x=T[ls].x+1; } void dfs(int x,int fa) { nl[x]=++dn; for(int i=head[x];i;i=e[i].next) if(e[i].to!=fa) dfs(e[i].to,x); nr[x]=dn; } void rebuild() { top=0; for(int i=1;i<=n;i++)b[nl[i]]=num[i]; for(int i=1;i<=n;i++)b[i]+=b[i-1]; for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[nr[i]]-b[nl[i]-1]; } void init() { dfs(rt,0); // for(int i=1;i<=n;i++) cout<<i<<" "<<nl[i]<<" "<<nr[i]<<endl; for(int i=1;i<=n;i++) { rt1[i]=++cc;rt2[i]=++cc; inst(rt1[i],rt1[i-1],nl[i]),inst(rt2[i],rt2[i-1],nr[i]); } } int main() { n=read();m=read(); for(int i=1;i<=n;i++) num[i]=read(); for(int i=1;i<=n;i++) { u=read();v=read(); if(u==0){rt=v;continue;} ins(u,v);ins(v,u); }init();rebuild(); for(int i=1;i<=m;i++) { op=read();u=read();v=read(); if(op==1){q[++top]=u;q2[top]=v-num[u];num[u]=v;} else { ans=sum[v]-sum[u-1]; for(int j=1;j<=top;j++) { ans+=1LL*q2[j]*(query(rt2[v],nl[q[j]])-query(rt2[u-1],nl[q[j]]) -query(rt1[v],nl[q[j]]+1)+query(rt1[u-1],nl[q[j]]+1)); } printf("%llu ",ans); } if(top>=50) rebuild(); } return 0; }
B.文艺计算姬
题意：求一个一边有n个点，另一边有m个点的完全二分图的生成树数量%p n,m,p<=10^18
题解：观察之后发现：答案是n^(m-1)*m^(n-1) 由于n,m非常大，所以手写一个大整数乘法就行了。
顺便一说，ditoly 0ms+代码短卡到rank1了，真的劲。复杂度（log^2n)
#include<iostream> #include<cstdio> #define ll unsigned long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } ll n,m,p; ll mul(ll a,ll b,ll mod) { ll sum=0; for(;b;b>>=1,a=(a<<1)%mod)if(b&1)sum=(sum+a)%mod; return sum; } ll pow(ll x,ll p,ll mod) { ll sum=1; for(ll i=x;p;p>>=1,i=mul(i,i,mod)) if(p&1) sum=mul(sum,i,mod); return sum; } int main() { n=read();m=read();p=read(); ll ans=mul(pow(n,m-1,p),pow(m,n-1,p),p); cout<<ans; return 0; }
C.有一个点位于(0,0)，你要把它移到(ex,ey)，有两种可用的移动，如果原来位于(x,y)的话分别可以让他移动到(x+a,y+b)和(x+c,y+d)a*d-b*c!=0
还有n个点是限制点，不能走，求移动的方案数。 n<=500,限制点的坐标绝对值<=500
题解： 考虑dp+容斥原理，预处理（解方程+组合数）出每两个点之间的方案数量，答案=方案数-走一个限制点的方案数+走两个限制点的方案-........
但这显然要求转移是有序的，我们发现题目只有两种可用的移动，所以我们可以考虑以其中一个向量为x轴，然后按照y坐标为第一关键字，x坐标为第二关键字乱排序一下（可以利用向量的点积和叉积），然后直接dp就没啦。
复杂度(nlogn+n^2)
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long #define mod 1000000007 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } ll q[500005],r[500005]; ll f[1005]; ll g[1005][1005]; double xie; int a,b,c,d; int ex,ey,n; struct node{ int x,y,nx,ny; }s[1005]; bool cmp1(node xx,node yy){return xx.nx<yy.nx||(xx.nx==yy.nx&&xx.ny<yy.ny);} bool cmp2(node xx,node yy){return xx.nx>yy.nx||(xx.nx==yy.nx&&xx.ny<yy.ny);} ll solve(int x,int y) { /* a*x1+c*x2=x b*x1+d*x2=y ab*x1+cb*x2=xb ab*x1+ad*x2=ya (ad-cb)*x2=ya-xb; x2=(yx-xb)/(da-cb) ad*x1+cd*x2=xd bc*x1+dc*x2=yc (bc-ad)x1=yc-xd */ int x2=a*y-x*b,y2=d*a-c*b; int x1=y*c-x*d,y1=b*c-a*d; // cout<<x<<" "<<y<<" "<<x2<<" "<<y2<<" "<<x1<<" "<<y1<<endl; if(x2%y2!=0||x1%y1!=0)return 0; x2/=y2;x1/=y1; if(x1<0||x2<0)return 0; ll sum=q[x1+x2]*r[x1]%mod*r[x2]%mod; return sum; } int main() { q[0]=1;r[0]=1;q[1]=r[1]=1; for(int i=2;i<=500000;i++){q[i]=q[i-1]*i%mod;r[i]=(mod-(mod/i))%mod*r[mod%i]%mod;} for(int i=2;i<=500000;i++)r[i]=r[i]*r[i-1]%mod; ex=read();ey=read();n=read(); a=read();b=read();c=read();d=read(); s[1].x=s[1].y=0;s[n+2].x=ex;s[n+2].y=ey; s[1].nx=0;s[n+2].nx=ey*a-ex*b; s[1].ny=0;s[n+2].ny=ex*a+ey*b; for(int i=2;i<=n+1;i++) { s[i].x=read();s[i].y=read(); s[i].nx=a*s[i].y-s[i].x*b; s[i].ny=s[i].x*a+s[i].y*b; } n+=2; if(a*d-b*c<0)sort(s+2,s+n,cmp2); else sort(s+2,s+n,cmp1); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) g[i][j]=solve(s[j].x-s[i].x,s[j].y-s[i].y); f[1]=-1; for(int i=2;i<=n;i++) for(int j=1;j<i;j++) f[i]=(f[i]-g[j][i]*f[j])%mod; while(f[n]<0)f[n]+=mod; cout<<f[n]; return 0; }