# noip模拟52 solutions

## T1 异或

0前面的就是当前的方案数，直接计算就好了

AC_code ``` #include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define int long long #define re register int int n; ull ans=0; signed main(){ scanf("%llu",&n);n--; for(re i=0;i<=60;i++){ int baf=((1ll<<i+1)-1); int bag=((1ll<<i)-1),res=0; if(bag<=n)res++; if((baf&n)<bag)res--; res+=(n>>i+1); if(res>0)ans+=res*(i+1); } printf("%llu",ans); } ```

## T2 赌神

AC_code ``` #include<bits/stdc++.h> using namespace std; #define int long long #define re register int const int N=1e6+5; const int mod=998244353; int n,num[N],ans,jc[N],sum; int ksm(int x,int y){ int ret=1; while(y){ if(y&1)ret=ret*x%mod; x=x*x%mod; y>>=1; } return ret; } int C(int x,int y){return jc[x]*ksm(jc[y]*jc[x-y]%mod,mod-2)%mod;} signed main(){ scanf("%lld",&n); for(re i=1;i<=n;i++)scanf("%lld",&num[i]),sum+=num[i]; ans=ksm(n,sum); jc[0]=1;for(re i=1;i<=sum;i++)jc[i]=jc[i-1]*i%mod; ans=ans*ksm(jc[sum],mod-2)%mod; for(re i=1;i<=n;i++)ans=ans*jc[num[i]]%mod; printf("%lld",ans); } ```

## T3 路径

AC_code ``` #include<bits/stdc++.h> using namespace std; #define ll long long #define int long long #define re register int const int N=1e6+100000; const int mod=998244353; int n,m,mxd,md; ll an[N],ans; ll s[N],t[N],o[N]; struct FFT{ struct coex{ double r,i; coex(){} coex(double x,double y){r=x;i=y;} coex operator + (coex x)const{return coex(r+x.r,i+x.i);} coex operator - (coex x)const{return coex(r-x.r,i-x.i);} coex operator * (coex x)const{return coex(r*x.r-i*x.i,r*x.i+i*x.r);} }a[N],b[N],w[N]; const double pi=acos(-1.0); int af[N],lim,len; void fft(coex a[]){ for(re i=0;i<lim;i++)if(af[i]>i)swap(a[i],a[af[i]]); for(re t=lim>>1,d=1;d<lim;d<<=1,t>>=1) for(re i=0;i<lim;i+=(d<<1)) for(re j=0;j<d;j++){ coex tmp=w[t*j]*a[i+j+d]; a[i+j+d]=a[i+j]-tmp; a[i+j]=a[i+j]+tmp; } } void mul(int ln,int lm){ for(lim=1,len=0;lim<=ln+lm;lim<<=1,len++); for(re i=0;i<lim;i++){ af[i]=(af[i>>1]>>1)|((i&1)<<(len-1)); w[i]=coex(cos(2.0*i*pi/lim),sin(2.0*i*pi/lim)); } for(re i=0;i<=ln;i++)a[i].r=1.0*s[i]; for(re i=0;i<=lm;i++)b[i].r=1.0*t[i]; fft(a);fft(b); for(re i=0;i<lim;i++)a[i]=a[i]*b[i],w[i].i=-w[i].i; fft(a); for(re i=0;i<lim;i++){ if(i<=ln+lm)o[i]=(int)(a[i].r/lim+0.5); a[i]=b[i]=w[i]=coex(0,0); } } }work; ll ksm(ll x,ll y){ ll ret=1; while(y){ if(y&1)ret=ret*x%mod; x=x*x%mod; y>>=1; } return ret; } int to[N*2],nxt[N*2],head[N],rp; void add_edg(int x,int y){ to[++rp]=y; nxt[rp]=head[x]; head[x]=rp; } int siz[N],rt,ms[N],mx; bool vis[N]; void get_rt(int x,int f,int sz){ ms[x]=0;siz[x]=1; for(re i=head[x];i;i=nxt[i]){ int y=to[i]; if(y==f||vis[y])continue; get_rt(y,x,sz); siz[x]+=siz[y]; ms[x]=max(ms[x],siz[y]); } ms[x]=max(ms[x],sz-siz[x]); if(ms[x]<mx)mx=ms[x],rt=x; } void dfs(int x,int f,int dep){ t[dep]++;md=max(md,dep); for(re i=head[x];i;i=nxt[i]){ int y=to[i]; if(y==f||vis[y])continue; dfs(y,x,dep+1); } } void sol(int x){ s[0]=1;mxd=0; for(re i=head[x];i;i=nxt[i]){ int y=to[i];md=0; if(vis[y])continue; dfs(y,x,1); work.mul(mxd,md); for(re j=0;j<=md;j++)s[j]=s[j]+t[j]%mod,t[j]=0; for(re j=0;j<=mxd+md;j++)an[j]=(an[j]+o[j])%mod; mxd=max(mxd,md); } for(re i=1;i<=mxd;i++)s[i]=0; } void divd(int x,int sz){ vis[x]=true;sol(x); for(re i=head[x];i;i=nxt[i]){ int y=to[i]; if(vis[y])continue; mx=0x3f3f3f3f; if(siz[y]<siz[x])get_rt(y,x,siz[y]),divd(rt,siz[y]); else get_rt(y,x,sz-siz[x]),divd(rt,sz-siz[x]); } } signed main(){ scanf("%lld%lld",&n,&m); for(re i=1;i<n;i++){ int x,y;scanf("%lld%lld",&x,&y); add_edg(x,y);add_edg(y,x); } mx=0x3f3f3f3f; get_rt(1,0,n); divd(rt,n); for(re i=1;i<=n;i++)ans=(ans+an[i]*ksm(i,m))%mod; printf("%lld",ans); } ```

## T4 树

60pts ``` #include<bits/stdc++.h> using namespace std; #define int long long #define re int const int N=3e6+5; const int B=550; int n,q,ans[N]; int to[N*4],nxt[N*4],head[N],rp; void add_edg(int x,int y){ to[++rp]=y; nxt[rp]=head[x]; head[x]=rp; } int dfn[N],dfm[N],cnt,idf[N],dep[N],mxd; void dfs_fi(int x,int f){ dfn[x]=++cnt;idf[cnt]=x; mxd=max(mxd,dep[x]); for(re i=head[x];i;i=nxt[i]){ int y=to[i]; if(y==f)continue; dep[y]=dep[x]+1; dfs_fi(y,x); } dfm[x]=cnt; } int typ[N],v[N],x[N],y[N],yy[N],z[N]; int bas,bel[N],l[B],r[B]; vector<int> one[B][B],two[N]; int so1[N],sol1[N],so2[N],sol2[N]; signed main(){ scanf("%lld%lld",&n,&q); for(re i=1;i<n;i++){ int u,v;scanf("%lld%lld",&u,&v); add_edg(u,v);add_edg(v,u); } dep[1]=1;dfs_fi(1,0);bas=sqrt(n); memset(l,0x3f,sizeof(l)); for(re i=1;i<=n;i++){ bel[i]=(i-1)/bas+1; l[bel[i]]=min(l[bel[i]],i); r[bel[i]]=max(r[bel[i]],i); } for(re i=1;i<=q;i++){ scanf("%lld",&typ[i]); if(typ[i]==1){ scanf("%lld%lld%lld%lld",&v[i],&x[i],&y[i],&z[i]); yy[i]=y[i];y[i]=(y[i]+dep[v[i]])%x[i]; if(x[i]<=bas){ if(!one[x[i]][y[i]].size())one[x[i]][y[i]].push_back(0); one[x[i]][y[i]].push_back(i); } else if(dep[v[i]]+yy[i]<=mxd)two[dep[v[i]]+yy[i]].push_back(i); } else { scanf("%lld",&v[i]); for(re j=1;j<=bas;j++)if(one[j][dep[v[i]]%j].size())one[j][dep[v[i]]%j].push_back(i); if(two[dep[v[i]]].size())two[dep[v[i]]].push_back(i); } } for(re i=1;i<=bas+1;i++){ for(re j=0;j<i;j++){ for(re k=1;k<one[i][j].size();k++){ int now=one[i][j][k]; if(typ[now]==1){ for(re o=max(dfn[v[now]],l[bel[dfn[v[now]]]]);o<=r[bel[dfn[v[now]]]];o++)so1[o]+=z[now]; for(re o=l[bel[dfm[v[now]]]];o<=min(dfm[v[now]],r[bel[dfm[v[now]]]]);o++)so1[o]+=z[now]; for(re o=bel[dfn[v[now]]]+1;o<bel[dfm[v[now]]];o++)sol1[o]+=z[now]; } else ans[now]+=so1[dfn[v[now]]]+sol1[bel[dfn[v[now]]]]; } for(re k=1;k<one[i][j].size();k++){ int now=one[i][j][k]; if(typ[now]==1){ for(re o=max(dfn[v[now]],l[bel[dfn[v[now]]]]);o<=r[bel[dfn[v[now]]]];o++)so1[o]-=z[now]; for(re o=l[bel[dfm[v[now]]]];o<=min(dfm[v[now]],r[bel[dfm[v[now]]]]);o++)so1[o]-=z[now]; for(re o=bel[dfn[v[now]]]+1;o<bel[dfm[v[now]]];o++)sol1[o]-=z[now]; } } } } for(re i=1;i<=mxd;i++){ if(!two[i].size())continue; sort(two[i].begin(),two[i].end()); for(re j=0;j<two[i].size();j++){ int now=two[i][j]; if(typ[now]==1){ so2[dfn[v[now]]]+=z[now]; sol2[bel[dfn[v[now]]]]+=z[now]; so2[dfm[v[now]]+1]-=z[now]; sol2[bel[dfm[v[now]]+1]]-=z[now]; if(i+x[now]<=mxd)two[i+x[now]].push_back(now); } else { for(re o=l[bel[dfn[v[now]]]];o<=min(r[bel[dfn[v[now]]]],dfn[v[now]]);o++)ans[now]+=so2[o]; for(re o=1;o<bel[dfn[v[now]]];o++)ans[now]+=sol2[o]; } } for(re j=0;j<two[i].size();j++){ int now=two[i][j]; if(typ[now]==1){ so2[dfn[v[now]]]-=z[now]; sol2[bel[dfn[v[now]]]]-=z[now]; so2[dfm[v[now]]+1]+=z[now]; sol2[bel[dfm[v[now]]+1]]+=z[now]; } } } for(re i=1;i<=q;i++)if(typ[i]==2)printf("%lld\n",ans[i]); } ```

noip模拟52[有一些不知]

(0)
(0)