刚从NEYC回来,才发现好久没写题解了。
T1
维护一个集合,支持插入一个数、删除一个数、全局加x(<=1e9)、查询二进制第k位为1的数有多少个。
我们只需要对值域开k个桶,每个范围是[0,2^k - 1],然后最高为为0或1的各占一半,我们只需要维护桶里元素个数就好了,用树状数组的话复杂度O(nk^2)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#pragma GCC optimize("-O3") #include <bits/stdc++.h> #define mxn 500005 using namespace std; char ibuf[65536],*ih,*it; #define getc() ((ih==it)&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it)?0:*ih++) inline int read(){ int s=0,f=1; char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc(); return s*f; } int n,op[mxn],ov[mxn],bit[32]; namespace pf0{ int s[mxn],tot; inline void pf20(){ for(int i=1;i<=n;++i) { if(op[i]==0) { s[++tot]=ov[i]; } else if(op[i]==1) { for(int j=1;j<=tot;++j) if(s[j]==ov[i]) s[j]=-1; } else if(op[i]==2) { for(int j=1;j<=tot;++j) if(s[j]>=0) s[j]+=ov[i]; } else if(op[i]==3) { int ans=0; for(int j=1;j<=tot;++j) if(s[j]>=0&&(s[j]&bit[ov[i]])) ++ans; printf("%d\n",ans); } } } } namespace pf1{ int ans[32]; unordered_map<int,int> mp; inline void pf20(){ for(int i=1;i<=n;++i) { if(op[i]==0) { for(int j=0;j<=18;++j) if(ov[i]&bit[j]) ++ans[j]; mp[ov[i]]++; } else if(op[i]==1) { register int tim=mp[ov[i]]; for(int j=0;j<=18;++j) if(ov[i]&bit[j]) ans[j]-=tim; mp[ov[i]]=0; } else if(op[i]==3) { printf("%d\n",ans[ov[i]]); } } } } int main(){ for(int i=0;i<=30;++i) bit[i]=1<<i; n=read(); bool flag=1; for(int i=1;i<=n;++i) { op[i]=read(),ov[i]=read(); if(op[i]==2) flag=0; } if(n<=1000) return pf0::pf20(),0; if(flag) return pf1::pf20(),0; pf0::pf20(); } |
T2
原题,不过考场被卡常了,刚好多了几十ms,加个记忆化跑的飞快(其实是忘了)。
参见这里。
T3
求n个点的无向图的联通块个数的k次方的期望。
考场上打的O(n^2logn)的NTT暴力,期望30,但第一个点WA了,可能是没特判K=0,也可能是别的边界。
正解做法比较神,假设我们有T个联通块,那么用斯特林数展开:
$$T^k = \sum _{i=1} ^{k} S(k,i) C(T,i) i!$$
之后,我们发现如果对于每个T都求的话,复杂度不能继续优化了,那么我们就尝试把T换掉。考虑这个式子的实际意义,其实是枚举非空集合的数量并分配元素。那么我们就可以把C换掉,也就是枚举点集,统计包含这样的特征的点集的图的个数,而这个玩意我们可以DP求。
首先求出f(n)表示n个点的带标号联通图的生成函数,g(n)表示n个点的任意无向图的方案数,那么\(g(n)=2^{C_{n}^{2}}\),\(f(n)=g(n) - \sum_{i=1}^{n-1}C_{n-1}^{i-1}f(i)g(n-i)\)。我们可以多项式求逆,求出所有的f。
设\(G=\sum_{i=0}^{n} \frac{g(i)}{(i-1)!} x^i \),\(F=\sum_{i=0}^{n}\frac{f(i)}{(i-1)!}x^i\),\(H=\sum_{i=0}^{n} \frac{g(i)}{(i)!} x^i \),那么有\(G-F=FH)\,这样就可以搞了。
设\(g_{i}(n)\)表示i个联通块的生成函数,那么对于i >= 2,有如下转移:
$$ g_{i}(n) = \sum_{j=1}^{n} C_{n-1}^{j-1}\,g_{1}(j)\,g_{i-1}(n-j)$$
接着,由于我们只需要求出来小于等于K个联通块的结果,所以我们就卷出来所有的g就好了。
最后,答案就是\(\sum_{i=1}^{k} S(k,i) i! \sum_{j=1}^{n}C_{n}^{j} g_{i}(j) 2^{C_{n-j}^{2}} \),再卷出来所有的答案数组,我们的预处理就做完了,复杂度O(nklog(n)),单次回答询问是O(k)。
一定要记得特判K=0。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#pragma GCC optimize("-O3") #include <bits/stdc++.h> #define ll long long #define mod 1004535809 #define P 1004535809 #define mxn 132005 using namespace std; char ibuf[65536],*ih,*it; #define getc() ((ih==it)&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it)?0:*ih++) inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*f; } inline ll qpow(ll a,ll b=mod-2){ ll ret=1; while(b){ if(b&1) ret=ret*a%mod; a=a*a%mod,b>>=1; } return ret; } int bit[32],rev[(1<<17)+5],mxl=1<<17; ll G[2][(1<<17)+5]; inline void ntt_init(){ register ll w=1,wn=qpow(3,(P-1)/mxl); for(int i=0;i<=mxl;++i,w=w*wn%P) G[0][i]=w; } inline void ntt_prep(int n){ for(int i=0;i<n;++i) { if(i&1) rev[i]=(rev[i>>1]>>1)|(n>>1); else rev[i]=rev[i>>1]>>1; } } inline void ntt(int *s,int n,int o) { register int i,j,l,m; for(i=0;i<n;++i) if(i>rev[i]) swap(s[i],s[rev[i]]); register int t,u; for(l=2,m=1;l<=n;m=l,l<<=1) { for(i=0;i<m;++i) G[1][i]=G[0][o==1?(mxl/l*i):(mxl-mxl/l*i)]; for(i=0;i<n;i+=l) for(j=0;j<m;++j) { t=s[i+j],u=G[1][j]*s[i+j+m]%P; s[i+j]=t+u,s[i+j]>=mod?s[i+j]-=mod:0; s[i+j+m]=t-u,s[i+j+m]<0?s[i+j+m]+=mod:0; } } if(o==-1) { register ll inv=qpow(n); for(i=0;i<n;++i) s[i]=1ll*s[i]*inv%P; } } int tp[(1<<17)+5]; inline void pl_inv(int *a,int *b,int n){ if(n==1) {b[0]=qpow(a[0]); return;} pl_inv(a,b,n>>1); ntt_prep(n<<1); memcpy(tp,a,sizeof(tp[0])*n),memset(tp+n,0,sizeof(tp[0])*n); ntt(tp,n<<1,1),ntt(b,n<<1,1); for(int i=0;i<(n<<1);++i) tp[i]=(1ll*b[i]*((2ll-1ll*tp[i]*b[i])%mod+mod))%mod; ntt(tp,n<<1,-1); memcpy(b,tp,sizeof(tp[0])*n),memset(b+n,0,sizeof(b[0])*n); } ll fac[mxn],inv[mxn],S[25][25]; inline int C(int N,int M){ if(M>N) return 0; return fac[N]*inv[M]%P*inv[N-M]%P; } int f[mxn],g[mxn],h[mxn],iv[mxn],to[16][mxn],as[16][mxn],e[mxn],d[mxn]; signed main(){ //freopen("B.out","w",stdout); ntt_init(); register int lim=50000; fac[0]=inv[0]=1; for(int i=1;i<=lim;++i) fac[i]=fac[i-1]*i%P; inv[lim]=qpow(fac[lim]); for(int i=lim-1;i>=1;--i) inv[i]=inv[i+1]*(i+1)%P; S[0][0]=1; for(int i=1;i<=15;++i) { S[i][1]=1; for(int j=2;j<=i;++j) S[i][j]=(S[i-1][j-1]+1ll*S[i-1][j]*j)%mod; } for(int i=0;i<=lim;++i) d[i]=h[i]=g[i]=e[i]=qpow(2,1ll*i*(i-1)>>1),h[i]=1ll*h[i]*inv[i]%mod,i?g[i]=1ll*g[i]*inv[i-1]%mod:0; for(int i=0;i<=lim;++i) e[i]=1ll*e[i]*inv[i]%mod; g[0]=0,h[0]=1; int len=1<<16; pl_inv(h,iv,len); for(int i=lim+1;i<len;++i) iv[i]=g[i]=0; len=1<<17,ntt_prep(len); ntt(g,len,1),ntt(iv,len,1); for(int i=0;i<len;++i) to[1][i]=1ll*g[i]*iv[i]%P; ntt(to[1],len,-1); for(int i=1;i<=lim;++i) to[1][i]=1ll*to[1][i]*fac[i-1]%P; for(int i=lim+1;i<len;++i) to[1][i]=0; memset(g,0,sizeof(g)); for(int i=1;i<=lim;++i) g[i]=to[1][i]*inv[i-1]%P; ntt(g,len,1),ntt(e,len,1); for(int i=2;i<=15;++i) { memset(h,0,sizeof(h[0])*len); for(int j=0;j<=lim;++j) h[j]=1ll*to[i-1][j]*inv[j]%P; ntt(h,len,1); for(int j=0;j<len;++j) h[j]=1ll*h[j]*g[j]%P; ntt(h,len,-1); for(int j=0;j<=lim;++j) to[i][j]=h[j]*fac[j-1]%P; } for(int i=1;i<=15;++i) { memset(h,0,sizeof(h[0])*len); for(int j=0;j<=lim;++j) h[j]=to[i][j]*inv[j]%P; ntt(h,len,1); for(int j=0;j<len;++j) h[j]=1ll*h[j]*e[j]%P; ntt(h,len,-1); for(int j=0;j<=lim;++j) as[i][j]=h[j]*fac[j]%P; } int cas=read(),x,y; register ll ans,res; while(cas--) { x=read(),y=read(),ans=0,res=0; if(!y) {puts("1"); continue;} for(int i=1;i<=y;++i) { res=0; ans+=as[i][x]%P*S[y][i]%P*fac[i]%P; } printf("%lld\n",ans%P*qpow(d[x])%P); } } |
叨叨几句... NOTHING