12.10 模拟赛
发布时间:2020-12-14 04:27:54 所属栏目:大数据 来源:网络整理
导读:T1 bishop 题目大意: n个点组成了一些环 在这n个点中等概率选k个点(不能重复) 染了一个点就会染该环上的所有点 求所有点都被染色的概率 思路: 可以设$F i j$? 表示在$i$个环放$k$个点的方案数即$F i j =C i j,if j==0 Fi j =0$ 我们考虑生成函数即合并
T1 bishop 题目大意: n个点组成了一些环 在这n个点中等概率选k个点(不能重复) 染了一个点就会染该环上的所有点 求所有点都被染色的概率 思路: 可以设$F i j$? 表示在$i$个环放$k$个点的方案数即$F i j =C i j,if j==0 Fi j =0$ 我们考虑生成函数即合并两个数组 发现是卷积 所以我们直接建出初始数组 然后分治一样两两卷积 就过了 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstring> 7 #include<vector> 8 #include<queue> 9 #include<map> 10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i) 11 #define dwn(i,t) for(register int i=(s);i>=(t);--i) 12 #define ren for(int i=fst[x];i;i=nxt[i]) 13 #define Fill(x,t) memset(x,t,sizeof(x)) 14 #define ll long long 15 #define inf 2139062143 16 #define MAXN 170100 17 #define MOD 998244353 18 using namespace std; 19 inline int read() 20 { 21 int x=0,f=1;char ch=getchar(); 22 while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();} 23 while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();} 24 return x*f; 25 } 26 int N,n,m,k,vis[MAXN],to[MAXN],sz[MAXN],tot; 27 int fac[MAXN],inv[MAXN],rev[MAXN<<2],inv3; 28 ll A[MAXN<<2],B[MAXN<<2],lmt,lg; 29 vector <int> vec[MAXN]; 30 void dfs(int x) {sz[tot]++,vis[x]=1;if(!vis[to[x]]) dfs(to[x]);} 31 ll q_pow(ll bas,ll t,ll res=1) 32 { 33 for(;t;t>>=1,(bas*=bas)%=MOD) 34 if(t&1) (res*=bas)%=MOD;return res; 35 } 36 int C(int n,int m) {return ((ll)((((ll)fac[n]*inv[m])%MOD)*inv[n-m]))%MOD;} 37 void ntt(ll *a,int n,int f) 38 { 39 rep(i,0,n-1) if(i<rev[i])swap(a[i],a[rev[i]]); 40 for(int i=1;i<n;i<<=1) 41 { 42 ll wn=q_pow(3,(MOD-1)/(i<<1))%MOD; 43 if(f==-1)wn=q_pow(wn,MOD-2); 44 for(int j=0;j<n;j+=i<<1) 45 { 46 ll w=1,x,y; 47 for(int k=0;k<i;k++,w=wn*w%MOD) 48 x=a[k+j],y=((ll)a[k+j+i]*w)%MOD,a[j+k]=(x+y)%MOD,a[j+k+i]=(x-y+MOD)%MOD; 49 } 50 } 51 if(f==1) return ;int nv=q_pow(n,MOD-2); 52 for(int i=0;i<n;i++) a[i]=a[i]*nv%MOD; 53 } 54 void Div(int l,int r,ll tmp) 55 { 56 if(l==r) return ;int mid=(l+r)>>1; 57 int t1=min(sz[mid]-sz[l-1],k-1),t2=min(sz[r]-sz[mid],k-1); 58 Div(l,mid,t1);Div(mid+1,r,t2);tmp=t1+t2;lmt=1,lg=0; 59 while(lmt<=tmp) lmt<<=1,lg++; 60 for(int i=0;i<lmt;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1)); 61 rep(i,t1) A[i]=vec[l][i];rep(i,t1+1,lmt-1) A[i]=0; 62 rep(i,t2) B[i]=vec[mid+1][i];rep(i,t2+1,lmt-1) B[i]=0;/* 63 rep(i,lmt-1) cout<<A[i]<<" ";cout<<endl; 64 rep(i,lmt-1) cout<<B[i]<<" ";cout<<endl;*/ 65 ntt(A,1);ntt(B,1); 66 rep(i,lmt) (A[i]*=B[i])%=MOD; 67 ntt(A,-1);vec[l].clear();vec[mid+1].clear(); 68 rep(i,0,min(tmp,(ll)k)) vec[l].push_back(A[i]); 69 } 70 int main() 71 { 72 freopen("bishop.in","r",stdin); 73 freopen("bishop.out","w",stdout); 74 int T=read(),x;inv[0]=inv[1]=fac[0]=1; 75 rep(i,2,152501) inv[i]=((ll)(MOD-MOD/i)*inv[MOD%i])%MOD;inv3=inv[3]; 76 rep(i,1,152501) fac[i]=((ll)fac[i-1]*i)%MOD,inv[i]=((ll)inv[i-1]*inv[i])%MOD; 77 while(T--) 78 { 79 Fill(vis,0);Fill(sz,0); 80 n=read(),k=read()+1,tot=0;rep(i,n) to[i]=read(); 81 rep(i,n) if(!vis[i]) tot++,dfs(i); 82 x=n,n=tot;rep(i,n) {vec[i].push_back(0);rep(j,min(sz[i],k-1)) vec[i].push_back(C(sz[i],j));} 83 //rep(i,1,n) {for(auto x:vec[i]) cout<<x<<" ";puts("");} 84 rep(i,n) sz[i]+=sz[i-1];//cout<<sz[1]<<" "<<sz[2]<<endl; 85 Div(1,k);printf("%lldn",((ll)(vec[1][k-1]*q_pow(C(x,MOD-2)))%MOD); 86 rep(i,1,n) vec[i].clear(); 87 } 88 fclose(stdout);return 0; 89 } ? T2 decoration 题目大意: ? T3 conference 题目大意: 一颗树 每个点有人数和边权 支持两个操作 1. 修改单点的人数 2.在$x-y$链上找一个点使得其他点的人走到这个点的距离和最小 输出这个距离 思路: 对于询问 要求的点为带权中位数 所以可以在ST表上二分来找到这个点 用两个树状数组分别维护每个点到根的人数和以及(该点人数*该点到根路径长度)到根的和 计算答案的时候加加减减即可 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstring> 7 #include<vector> 8 #include<queue> 9 #include<map> 10 #define rep(i,t) for(register int i=(s);i>=(t);--i) 12 #define ren for(register int i=fst[x];i;i=nxt[i]) 13 #define Fill(x,sizeof(x)) 14 #define ll long long 15 #define inf 2139062143 16 #define MOD 998244353 17 #define MAXN 170100 18 using namespace std; 19 inline int read() 20 { 21 int x=0,f=1;char ch=getchar(); 22 while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();} 23 while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();} 24 return x*f; 25 } 26 int n,v[MAXN],fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1],f[MAXN][20]; 27 int dep[MAXN],in[MAXN],ou[MAXN],tot,cnt; 28 ll dis[MAXN],tmp; 29 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;} 30 void dfs(int x,int pa) 31 { 32 for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1];in[x]=++tot; 33 ren if(to[i]!=pa) 34 dep[to[i]]=dep[x]+1,dis[to[i]]=dis[x]+val[i],f[to[i]][0]=x,dfs(to[i],x); 35 ou[x]=tot; 36 } 37 inline int lca(int u,int v) 38 { 39 if(dep[u]<dep[v]) swap(u,v);int t=dep[u]-dep[v]; 40 dwn(i,19,0) if((1<<i)&t) u=f[u][i];if(u==v) return u; 41 dwn(i,0) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; 42 return f[u][0]; 43 } 44 struct Fenwick 45 { 46 ll c[MAXN]; 47 inline int lowbit(int x) {return x&(-x);} 48 inline void mdf(int x,ll val) {for(;x<=n;x+=lowbit(x)) c[x]+=val;} 49 inline ll query(int x) {if(x<=0) return 0LL;ll res=0;for(;x;x-=lowbit(x)) res+=c[x];return res;} 50 }c1,c2; 51 void mdfc(int x,int t) 52 { 53 c1.mdf(in[x],t);c1.mdf(ou[x]+1,-t); 54 c2.mdf(in[x],t*dis[x]);c2.mdf(ou[x]+1,-t*dis[x]);v[x]+=t; 55 } 56 ll cheque(int x,int z,int i) 57 { 58 int t1=dep[x]-dep[z]; 59 if((1<<i)<=t1) return tmp=c1.query(in[x])-c1.query(in[f[x][i]]); 60 else return tmp=1LL<<60; 61 } 62 ll calc(int x,int anc){return c2.query(in[x])-c2.query(in[anc])-dis[anc]*(c1.query(in[x])-c1.query(in[anc]));} 63 ll work(int x,int y) 64 { 65 int z=lca(x,y),sum=c1.query(in[x])+c1.query(in[y])-(c1.query(in[z])<<1)+v[z],res=0,pos;sum=ceil(sum/2.0); 66 if(v[x]>=sum) res=pos=x,res=1; 67 else if(v[y]>=sum) res=pos=y,res=0; 68 else if(c1.query(in[x])-c1.query(in[z])>=sum){pos=x;dwn(i,0) if(res+cheque(x,z,i)<sum) x=f[x][i],res+=tmp;res=1;} 69 else {pos=y;dwn(i,0) if(res+cheque(y,i)<sum) y=f[y][i],res+=tmp;res=0;} 70 if(res) res=x,x=pos;else res=y,y=pos,swap(x,y);ll ans=0; 71 ans=calc(y,z)+(dis[res]-dis[z])*(c1.query(in[y])-c1.query(in[z]))+calc(x,res); 72 ans+=(dis[res]-dis[z])*(c1.query(in[res])-c1.query(in[z])+v[z])-calc(res,z); 73 return ans; 74 } 75 int main() 76 { 77 freopen("conference.in",stdin); 78 freopen("conference.out",stdout); 79 n=read();int a,b,c;rep(i,n) v[i]=read(); 80 rep(i,n) a=read(),b=read(),c=read(),add(a,c),add(b,a,c); 81 dfs(1,0);rep(i,n) mdfc(i,v[i]),v[i]>>=1;m=read(); 82 while(m--) 83 { 84 c=read(),a=read(),b=read(); 85 if(c==1) printf("%lldn",work(a,b));else mdfc(a,b-v[a]); 86 } 87 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |