[考试反思]0420省选模拟75:安在

[考试反思]0420省选模拟75:安在

[考试反思]0420省选模拟75:安在

好像并没有什么突出的表现,但是不知道为什么名次居然苟上来了。

可能是昨天放假今天大家的状态比较差(被动技能:熬夜引起的状态削减效果降低$65\%$)

$T1$是一个貌似比较靠直觉的题,顺着第一反应想到了。

$T2$推式子只想到一半,然后把$n^2log$优化成$O(n)$多拿$30$然而特判写错又挂掉$10$分。

$T3$剩的时间不够就没弄。

大体还行吧。困死了。

 

T1:比特币

大意:维护多重集支持插入,删除所有等于$x$的值,所有数$+x$,查询集合中有多少二进制第$k$位是$1$的数。$k <18,n\le 5\times 10^5,x \le 10^9$

一看到$x$这么大$k$这么小,第一反应是取模,多出的位显然没用。

发现答案只与$k$有关且$k$很小所以我们对于每个$k$维护答案。

直接弄$k$个树状数组,每个是模$2^{i+1}$意义下的,要查询$[2^i,2^{i+1})$的权值和。

所有数加的话只需要全局弄一个标记。多重清空只要用$map$存一下每个原数出现次数。

我弱智写了个线段树。写的又长跑得又慢。时间复杂度$O(nk^2)$

[考试反思]0420省选模拟75:安在[考试反思]0420省选模拟75:安在
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 map<ll,int>M;
 5 struct Segment_Tree{
 6     int w[1<<20],B;
 7     #define lc p<<1
 8     #define rc lc|1
 9     #define md (L+R>>1)
10     void add(int x,int v,int p,int L,int R){
11         w[p]+=v; if(L==R)return;
12         if(x<=md)add(x,v,lc,L,md);else add(x,v,rc,md+1,R);
13     }
14     int ask(int l,int r,int p,int L,int R){
15         if(l<=L&&R<=r)return w[p];
16         return (l<=md?ask(l,r,lc,L,md):0)+(r>md?ask(l,r,rc,md+1,R):0);
17     }
18     int ask(int l,int r){return l<=r?ask(l,r,1,0,B):ask(l,B,1,0,B)+ask(0,r,1,0,B);}
19     void add(int x,int v){add(x,v,1,0,B);}
20 }T[18];
21 int mo(ll x,int b){b=1<<b+1;return (x%b+b)%b;}
22 int main(){
23     for(int i=0;i<=17;++i)T[i].B=(1<<i+1)-1;
24     int n,op;ll x,tag=0;
25     cin>>n;
26     while(n--){
27         scanf("%d%lld",&op,&x);
28         if(op==0){
29             x-=tag;M[x]++;
30             for(int i=0;i<=17;++i)T[i].add(mo(x,i),1);
31         }else if(op==1){
32             x-=tag;int t=M[x];M[x]=0;
33             for(int i=0;i<=17;++i)T[i].add(mo(x,i),-t);
34         }else if(op==2)tag+=x;
35         else printf("%d\n",T[x].ask(mo((1<<x)-tag,x),mo((1<<x+1)-1-tag,x)));
36     }
37 }
View Code

 

T2:测试

大意:$\sum\limits_{i=1}^{A}\sum\limits_{j=1}^{B}\sum\limits_{k=1}^{C}d(ijk),A,B,C \le 10^5$

经久不衰的结论:$d(nm)=\sum\limits_{i|n}\sum\limits_{j|m}[(i,j)=1]$

含义理解的话,就是考虑所有因子的分配。因为要求$ij$互质,所以说因子一定只分配在一边。

我们认定,如果对于质因子$p$,$n,m,i,j$中分别有$x,y,a,b$个。

那么如果$a=0,b \neq 0$则我们认为这对$(i,j)$对应着一个有$p^{x+b}$的数。否则对应$p^{a}$

这样所有因数都与一个$(i,j)$对应了。

这个结论可以扩展到$3$个数,也即$d(xyz)=\sum\limits_{i|x}\sum\limits_{j|y}\sum\limits_{k|z} [(i,j)=1][(i,k)=1][(j,k)=1]$

那么原问题经过一些简单的操作就会变为:$ans=\sum\limits_{i=1}^{A} \frac{A}{i} \sum\limits_{j=1}^{B} \frac{B}{j} \sum\limits_{k=1}^{C} \frac{C}{k} [(i,j)=1][(i,k)=1][(j,k)=1]$

莫反一下就是$\sum\limits_{d=1} \mu(d) \sum\limits_{z=1}^{C} \frac{C}{z} [(d,z)=1] \sum\limits_{x=1}^{\frac{A}{d}} \frac{A}{dx} [(x,z)=1] \sum\limits_{y=1}^{\frac{B}{d}} \frac{B}{dy} [(y,z)=1]$

递推处理$gcd$关系,这个式子暴力做能做到$O(n^2)$

[考试反思]0420省选模拟75:安在[考试反思]0420省选模拟75:安在
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define S 8001
 4 #define ui unsigned int
 5 bool g[S][S],np[S];int p[S],pc,mu[100005],A,B,C,oA[S],oB[S],cA,cB,rA[188],rB[188];
 6 ui G[100005],fA[S][188],fB[S][188],ans;
 7 vector<int>D[S];
 8 int main(){
 9     cin>>A>>B>>C;
10     mu[1]=1;
11     for(int i=2;i<S;++i){
12         if(!np[i])p[++pc]=i,mu[i]=-1;
13         for(int j=1;i*p[j]<S;++j)
14             if(i%p[j])np[i*p[j]]=1,mu[i*p[j]]=-mu[i];
15             else{np[i*p[j]]=1;break;}
16     }
17     for(int i=1;i<S;++i)for(int j=i;j<S;j+=i)D[j].push_back(i);
18     for(int i=1;i<S;++i)for(int j=1,I,l;I=i/j,j<=i;j=l+1)l=i/I,G[i]+=(l-j+1)*I; 
19     for(int i=A;i;--i)if(!oA[A/i])rA[oA[A/i]=++cA]=A/i;
20     for(int i=B;i;--i)if(!oB[B/i])rB[oB[B/i]=++cB]=B/i;
21     for(int i=2;i<=A&&i<=B;++i){
22         if(!np[i])for(int j=i;j<=C;j+=i)g[i][j]=1;
23         else{int x=D[i][1],y=i/x;for(int j=2;j<=C;++j)g[i][j]=g[x][j]|g[y][j];}
24     }
25     for(int z=1;z<=C;++z)for(int i=1;i<=cA;++i)for(int j=0;j<D[z].size();++j)fA[z][i]+=mu[D[z][j]]*G[rA[i]/D[z][j]];
26     for(int z=1;z<=C;++z)for(int i=1;i<=cB;++i)for(int j=0;j<D[z].size();++j)fB[z][i]+=mu[D[z][j]]*G[rB[i]/D[z][j]];
27     for(int d=1,a,b;a=oA[A/d],b=oB[B/d],d<=A&&d<=B;++d)if(mu[d])for(int z=1;z<=C;++z)if(!g[d][z])ans+=fA[z][a]*fB[z][b]*mu[d]*(C/z);
28     cout<<ans<<endl;
29 }
View Code

我们设$f_x(n)=\sum\limits_{i=1}^{n} [(i,x)=1] \mu(i),g_x(n)=\sum\limits_{i=1}^{n} [(i,x)=1] \frac{n}{i}$

则原式为$ans=\sum\limits_{x=1}^{A} \frac{A}{x} \sum\limits_{d=1}^{B} [(x,d)=1] \mu(d) g_x(\frac{B}{d}) g_x(\frac{C}{d})$

枚举$x$,将$d$整除分块,用定义的$f$前缀和做差求区间和,如果后面能够在合法复杂度内预处理得到那么总复杂度就是$O(n\sqrt{n})$

考虑如何预处理$f,g$:首先不难发现对于所有的$x$,我们把它的所有出现次数超过$1$的质因子次数都调整为$1$,$f,g$均不变

那么只需要考虑每种质因子都只包含一个的情况。对于一个数$x$设其一个质因子为$p$

因为我们知道不含平方因子后$(\frac{p}{x},x)=1$,所以我们直接考虑去掉质因子的所有倍数的贡献即可

列式化简可以得到$f_x(n)=f_{\frac{x}{p}}(n) + f_x(\frac{n}{p}),g_x(n)=g_{\frac{x}{p}}(n) + g_{\frac{x}{p}}(\frac{n}{p}) $

然后我们可以简单的预处理$f_1(n),g_1(n)$

且上面涉及到的所有的$n$都是整除分块时产生的数,总共有$O(\sqrt{n})$个。

所以只要最开始把所有整除分块涉及的值提出来对这些数做上面的$dp$。

然而存不下,所以我们采用搜索,每次添加一个质因数那样。

总复杂度就控制在了$O(n\sqrt{n})$。常数有点大。

[考试反思]0420省选模拟75:安在[考试反思]0420省选模拟75:安在
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ui unsigned int
 4 #define S 100001
 5 int p[S],pc,np[S],lp[S],ep[S],mu[S],_[S],c,v[S],A,B,C;
 6 ui sum[S],tot[S],ans,F[33][2333],G[33][2333];
 7 vector<int>pr;
 8 void sch(int x,int Lp,int d){
 9     for(int i=1,r;i<=B;i=r+1)r=min(B/(B/i),C/(C/i)),ans+=tot[x]*(F[d][_[r]]-F[d][_[i-1]])*G[d][_[B/i]]*G[d][_[C/i]];
10     for(int i=Lp,P;x*1ll*(P=pr[i])<=A;++i){
11         for(int j=1,n;n=v[j];++j)F[d+1][j]=F[d][j]+F[d+1][_[n/P]],G[d+1][j]=G[d][j]-G[d][_[n/P]];
12         sch(x*P,i+1,d+1);
13     }
14 }
15 int main(){
16     cin>>A>>B>>C; if(A>C)swap(A,C); if(A>B)swap(A,B); if(B>C)swap(B,C);
17     for(int i=2;i<=C;++i){
18         if(!np[i])p[++pc]=i,lp[i]=ep[i]=i,mu[i]=-1,pr.push_back(i);
19         for(int j=1,x;(x=i*p[j])<=C;++j)
20             if(i%p[j])lp[x]=p[j],ep[x]=ep[i]*p[j],mu[x]=-mu[i],np[x]=1;
21             else {lp[x]=p[j];np[x]=1;ep[x]=ep[i];break;}
22     }pr.push_back(C+1);
23     for(int i=lp[1]=ep[1]=mu[1]=1;i<=C;++i)mu[i]+=mu[i-1];
24     for(int x=1;x<=A;++x)tot[ep[x]]+=A/x;
25     for(int i=1,r,N;N=B/i,i<=B;i=r+1)r=B/N,v[++c]=N;
26     for(int i=1,r,N;N=C/i,i<=C;i=r+1)r=C/N,v[++c]=N;
27     sort(v+1,v+1+c); c=unique(v+1,v+1+c)-v-1;
28     for(int i=1;i<=c;++i){
29         _[v[i]]=i,F[0][i]=mu[v[i]],G[0][i]=sum[v[i]];
30         for(int j=1,N,r;N=v[i]/j,j<=v[i];j=r+1)r=v[i]/N,G[0][i]+=N*(r-j+1);
31     }sch(1,0,0); cout<<ans<<endl;
32 }
View Code

好像只有我是写的题解做法。$LNC$的神奇做法常数更小一些可以去看,懒得套娃了。

 

T3:光图

大意:求$n$点所有带标号无向图的联通块数的$k$次方之和。多测。$T \le 10^5,n \le 5\times 10^4,k \le 15$

前置:fft1专题《城市规划》。(这次写的是一个$log$的多项式求逆做法,可以再回去翻$LNC$大神的博客)

求出所有带标号联通图个数之后。考虑这道题。

假如联通块数是$T$则$T^k=(1+1+1+...+1)^k$。也就是说,从$T$个$1$中随便可重复的选择$k$次的方案数。

枚举我们一共选到了几种。$ans=\sum\limits_{i=1}^{k} \begin{bmatrix} k \\ i \end{bmatrix} i! \binom{T}{i}$

把$T$拿出来,如此考虑含义:我们枚举一个由$i$个联通块构成的集合。我们考虑有多少个图里包含了这样的集合。

首先加入我们能求出$g_i(n)$表示$i$个联通块$n$个点的图的个数。

那么$ans=ans=\sum\limits_{i=1}^{k} \begin{bmatrix} k \\ i \end{bmatrix} i! \sum\limits_{j=1}^{n} g_i(j) 2^{\binom{n-j}{2}} \binom{n}{j}$

也就是选出若干点构成特定形状作为枚举的联通块集合,剩下的部分随意连边。

这样可以$O(k)$回答单次询问。

问题只剩下如何求出$g$。首先$g_1$就是《城市规划》

$g_t(x) = g_1(i) g_{t-1}(x-i) \binom{x-1}{i-1}$

组合数是一个钦定。

总的时间复杂度是$O(knlogn)$

[考试反思]0420省选模拟75:安在[考试反思]0420省选模拟75:安在
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mod 1004535809
 4 #define S 262144
 5 int rev[S],r[S],n,A[S],B[S],fac[S],inv[S],G0[S],G1[S],F[16][S],FR[S],s[16][16],E[16][S],len,pw[S];
 6 int mo(int x){return x>=mod?x-mod:x;}
 7 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;}
 8 void NTT(int*a,int op=1){
 9     for(int i=1;i<len;++i)if(rev[i]>i)swap(a[i],a[rev[i]]);
10     for(int i=1;i<len;i<<=1)for(int j=0,w=qp(3,(mod-1)/2/i*op+mod-1);j<len;j+=i<<1)
11         for(int k=j,x,y,t=1;k<j+i;++k,t=1ll*t*w%mod)
12             x=a[k],y=a[k+i]*1ll*t%mod,a[k]=mo(x+y),a[k+i]=mo(x-y+mod);
13     if(op-1)for(int iv=qp(len,mod-2),i=0;i<len;++i)a[i]=1ll*a[i]*iv%mod;
14 }
15 void sat(int n){
16     len=1; while(len<=n)len<<=1;
17     for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
18 }
19 void Inv(int*a,int n){
20     if(n==1){r[0]=qp(a[0],mod-2);return;}
21     Inv(a,n+1>>1); sat(n<<1);
22     for(int i=0;i<len;++i)A[i]=i<n?a[i]:0;
23     for(int i=0;i<len;++i)B[i]=r[i];
24     NTT(A);NTT(B);
25     for(int i=0;i<len;++i)r[i]=(B[i]+B[i]-1ll*B[i]*A[i]%mod*B[i]%mod+mod)%mod;
26     NTT(r,-1);
27     for(int i=n+1;i<len;++i)r[i]=0;
28 }
29 int main(){
30     for(int i=0;i<=50000;++i)pw[i]=qp(2,i*(i-1ll)/2);
31     s[0][0]=1;
32     for(int i=1;i<=15;++i)for(int j=1;j<=i;++j)s[i][j]=(s[i-1][j-1]+1ll*s[i-1][j]*j)%mod;
33     for(int i=fac[0]=1;i<=50000;++i)fac[i]=fac[i-1]*1ll*i%mod;
34     inv[50000]=qp(fac[50000],mod-2);
35     for(int i=49999;~i;--i)inv[i]=inv[i+1]*(i+1ll)%mod;
36     for(int i=0;i<=50000;++i)G1[i]=pw[i]*1ll*inv[i]%mod,G0[i]=pw[i]*1ll*(i?inv[i-1]:0)%mod;
37     Inv(G1,50001);sat(100000); NTT(r); NTT(G0);
38     for(int i=0;i<len;++i)FR[i]=1ll*G0[i]*r[i]%mod; NTT(FR,-1); FR[0]=0;
39     for(int i=0;i<len;++i)F[1][i]=1ll*FR[i]*fac[i-1]%mod;
40     for(int i=50001;i<len;++i)FR[i]=0;
41     NTT(FR);
42     for(int t=2;t<=15;++t){
43         for(int i=0;i<len;++i)A[i]=0;
44         for(int i=1;i<=50000;++i)A[i]=F[t-1][i]*1ll*inv[i]%mod;
45         NTT(A); for(int i=0;i<len;++i)A[i]=1ll*A[i]*FR[i]%mod; NTT(A,-1);
46         for(int i=1;i<=50000;++i)F[t][i]=A[i]*1ll*fac[i-1]%mod;
47     }
48     for(int t=1;t<=15;++t){
49         for(int i=0;i<len;++i)A[i]=B[i]=0;
50         for(int i=0;i<=50000;++i)A[i]=pw[i]*1ll*inv[i]%mod,B[i]=F[t][i]*1ll*inv[i]%mod;
51         NTT(A);  NTT(B); for(int i=0;i<len;++i)E[t][i]=A[i]*1ll*B[i]%mod; NTT(E[t],-1);
52         for(int i=0;i<len;++i)E[t][i]=1ll*E[t][i]*fac[i]%mod;
53     }
54     int t,n,k,ans;cin>>t;while(t--){
55         ans=0;scanf("%d%d",&n,&k);
56         if(!k){puts("1");continue;}
57         for(int i=1;i<=k;++i)ans=(ans+1ll*s[k][i]*fac[i]%mod*E[i][n])%mod;
58         printf("%lld\n",ans*1ll*qp(pw[n],mod-2)%mod);
59     }
60 }
View Code

 

上一篇:901. 股票价格跨度


下一篇:团队冲刺第二阶段第十天