noip模拟52[有一些不知]

noip模拟52 solutions

不写总结了,没有时间了,直接上正解

T1 异或

你发现\(+1\)之后有影响的只是第一个0后面的数,所以枚举这个0的位置,

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 路径

这个我是FFT+点分治做的,直接优化一下找到距离为k的点对有多少

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 树

直接根号分治,小于的用一种,大于的用另外一种

这样的做法很常见吧

放上我被zero4338卡掉的代码

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]);
}
上一篇:获取哪一年 周一的所有日期


下一篇:52、Java JUC