好像并没有什么突出的表现，但是不知道为什么名次居然苟上来了。
可能是昨天放假今天大家的状态比较差（被动技能：熬夜引起的状态削减效果降低$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)$
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)$
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})$。常数有点大。
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)$
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