【比赛链接】http://59.61.75.5:8018/contest/216
A. 旅行
【题意】有一棵 $n$ 个节点的树，给定其中 $K$ 个节点，对所有的 $i$，求从节点 $i$ 出发，经过这 $K$ 个节点的最短路程。
【数据范围】$Kle nle 5 imes 10^5,1le wle 10^6$。
【题解】
不难发现，答案即为 $K$ 个点和点 $i$ 所构成的虚树路径和的两倍减去 $i$ 到 $K$ 个点的最大距离。
两遍 $dfs$ 转移树形 $dp$ 即可。
效率 $O(n)$。期望得分：100。
【代码】
1 #include<bits/stdc++.h> 2 const int inf=1<<30; 3 const int maxn=500000+10; 4 struct edge { int v,nxt,w; } e[maxn<<1]; 5 int siz[maxn],h[maxn],cnt,n,k; 6 bool flag[maxn]; 7 long long f[maxn],g[maxn],max1[maxn],max2[maxn],max[maxn]; 8 inline void dfs ( int u,int fr ) 9 { 10 siz[u]=flag[u];max1[u]=flag[u]?0:-inf;max2[u]=-inf; 11 for ( int i=h[u];i;i=e[i].nxt ) if ( e[i].v!=fr ) 12 { 13 dfs(e[i].v,u);siz[u]+=siz[e[i].v]; 14 if ( siz[e[i].v] ) f[u]+=f[e[i].v]+e[i].w; 15 if ( max1[e[i].v]+e[i].w>max1[u] ) max2[u]=max1[u],max1[u]=max1[e[i].v]+e[i].w; 16 else if ( max1[e[i].v]+e[i].w>max2[u] ) max2[u]=max1[e[i].v]+e[i].w; 17 } 18 } 19 inline void DFS ( int u,int fr ) 20 { 21 for ( int i=h[u];i;i=e[i].nxt ) if ( e[i].v!=fr ) 22 { 23 g[e[i].v]=f[u]+g[u]+e[i].w; 24 if ( siz[e[i].v] ) g[e[i].v]-=f[e[i].v]+e[i].w; 25 if ( k-siz[e[i].v] ) 26 { 27 max[e[i].v]=max[u]+e[i].w; 28 if ( max1[e[i].v]+e[i].w!=max1[u] ) max[e[i].v]=std::max(max[e[i].v],max1[u]+e[i].w); 29 else max[e[i].v]=std::max(max[e[i].v],max2[u]+e[i].w); 30 } 31 DFS(e[i].v,u); 32 } 33 } 34 signed main() 35 { 36 scanf("%d%d",&n,&k); 37 for ( int i=1,u,v,w;i<n;i++ ) 38 scanf("%d%d%d",&u,&v,&w), 39 e[++cnt].nxt=h[u],e[h[u]=cnt].v=v,e[cnt].w=w, 40 e[++cnt].nxt=h[v],e[h[v]=cnt].v=u,e[cnt].w=w; 41 for ( int i=1;i<=n;i++ ) max[i]=-inf; 42 for ( int i=1,u;i<=k;i++ ) scanf("%d",&u),flag[u]=true,max[u]=0; 43 dfs(1,0);DFS(1,0); 44 for ( int i=1;i<=n;i++ ) printf("%lld ",(f[i]+g[i])*2-std::max(std::max(max1[i],max2[i]),max[i])); 45 return 0; 46 }
B. 求和
【题意】令 $f(n)=sum_{i=1}^{n} sum_{j=1}^{n} g c d(i, j, n)$，求 $sum_{i=1}^n f(i) mod P$。
【数据范围】$1le nle 10^9, Ple 10^9+9$，$P$ 是质数。
【题解】
$f(i)=sumlimits_{d|i}sumlimits_{j=1}^{frac{i}{d}}sumlimits_{k=1}^{frac{i}{d}}dsumlimits_{e|gcd(frac{i}{d},j,k)}mu(e) xlongequal[quad]{T=de}sumlimits_{T|i}sumlimits_{d|T}dmu(frac{T}{d})(frac{i}{T})^2=sumlimits_{T|i}varphi(T)(frac{i}{T})^2=sumlimits_{T|i}varphi(frac{i}{T})T^2$
$sumlimits_{i=1}^{n}f(i)=sumlimits_{i=1}^nsumlimits_{T|i}varphi(frac{i}{T})T^2=sumlimits_{T=1}^n T^2sumlimits_{i=1}^{lfloorfrac{n}{T} floor}varphi(i)$
直接整除分块+杜教筛求 $phi$ 的前缀和即可。
期望得分：100。
【代码】
1 #include<bits/stdc++.h> 2 const int maxn=5000000+10; 3 int n,m=5000000,mod,inv6,inv2; 4 inline int power ( int x,int y ) 5 { 6 int z=1; 7 for ( ;y;y>>=1,x=1LL*x*x%mod ) if ( y&1 ) z=1LL*z*x%mod; 8 return z; 9 } 10 inline int sum ( int x ) { return 1LL*x*(x+1)%mod*(2*x+1)%mod*inv6%mod; } 11 long long mu[maxn],phi[maxn]; 12 int pr[maxn],tot; 13 bool flag[maxn]; 14 std::unordered_map<int,long long> map; 15 inline long long calc ( int n ) 16 { 17 if ( n<=m ) return phi[n]; 18 if ( map.count(n) ) return map[n]; 19 long long res=0; 20 for ( int i=2,j;i<=n;i=j+1 ) j=n/(n/i),res=(res+(j-i+1)%mod*calc(n/i))%mod; 21 res=(1LL*n*(n+1)%mod*inv2%mod-res+mod)%mod; 22 return map[n]=res; 23 } 24 signed main() 25 { 26 scanf("%d%d",&n,&mod);inv6=power(6,mod-2);inv2=power(2,mod-2); 27 mu[1]=phi[1]=1; 28 for ( int i=2;i<=m;i++ ) 29 { 30 if ( !flag[i] ) pr[++tot]=i,mu[i]=-1,phi[i]=i-1; 31 for ( int j=1;j<=tot and pr[j]*i<=m;j++ ) 32 { 33 flag[pr[j]*i]=true; 34 if ( !(i%pr[j]) ) { mu[pr[j]*i]=0;phi[pr[j]*i]=phi[i]*pr[j];break; } 35 mu[pr[j]*i]=-mu[i];phi[pr[j]*i]=phi[i]*(pr[j]-1); 36 } 37 } 38 for ( int i=2;i<=m;i++ ) phi[i]=(phi[i-1]+phi[i])%mod; 39 int ans=0; 40 for ( int i=1,j;i<=n;i=j+1 ) j=n/(n/i),ans=(ans+1LL*sum(n/i)*(calc(j)-calc(i-1)+mod))%mod; 41 return !printf("%d ",ans); 42 }
C. 递增
【题意】已知 $l_{1dots n}$ 和 $r_{1dots n}$，求所有满足以下条件的序列 ${a_n}$ 的元素和的和：对任意 $iin[1,n]$ 满足 $l_ile a_ile r_i$，且 ${a_n}$ 是非严格递增的。
【数据范围】$2le nle 50, 0le l_ile r_i< 2^{60}$。
【题解】
考虑先将 $l,r$ 离散化。为了处理方便离散化所有的 $l_i$ 和 $r_i+1$。记离散化后的权值数组为 $val_i$，对应区间 $[val_i,val_{i+1}-1]$。
显然原来的每段可以拆分成若干个小区间。根据题目要求，$a_n$ 所在的小区间编号单调不降。
考虑 $dp$，记 $f_{i,j}$ 表示前 $i$ 个元素，第 $i$ 个元素在第 $j$ 个小区间内的元素和。显然可以枚举 $k,l$，从 $f_{k,l}$ 转移。
考虑转移。根据转移，$[k+1,i]$ 中的元素都必须在区间 $[val_j,val_{j+1}-1]$ 内。记元素的取值范围区间为 $[L,R]$，共需要取 $t=i-k$ 个元素。
显然转移的方案数为 $cnt=C_{R-L+t}^t$，根据数列相关知识，所有转移方案的权值总和为 $sum=t imes frac{L+R}{2} imes cnt$。
发现无法直接转移，因此需记录 $g_{i,j}$ 表示前 $i$ 个元素，第 $i$ 个元素在第 $j$ 个小区间内的方案数。
则有：$$f_{i,j}=sum cnt imes f_{k,l}+sum*g_{k,l},g_{i,j}=sum cnt imes g_{k,l}$$。直接转移即可。
效率 $O(n^4)$。期望得分：100。
【代码】
1 #include<bits/stdc++.h> 2 const long long mod=998244353,inv2=(mod+1)>>1; 3 std::set<long long> s; 4 std::unordered_map<long long,int> map; 5 int n,tot,L[500],R[500]; 6 long long l[500],r[500],val[500],f[500][500],g[500][500],ans,inv[500]; 7 inline long long C ( long long x,int y ) 8 { 9 long long res=inv[y]; 10 for ( int i=1;i<=y;i++ ) (res*=(x-i+1)%mod)%=mod; 11 return res; 12 } 13 signed main() 14 { 15 scanf("%d",&n);inv[0]=inv[1]=1; 16 for ( int i=1;i<=n;i++ ) scanf("%lld",&l[i]),s.insert(l[i]); 17 for ( int i=1;i<=n;i++ ) scanf("%lld",&r[i]),s.insert(r[i]+1); 18 for ( int i=2;i<=n;i++ ) inv[i]=(mod-mod/i)*inv[mod%i]%mod; 19 for ( int i=2;i<=n;i++ ) (inv[i]*=inv[i-1])%=mod; 20 for ( long long x:s ) val[map[x]=++tot]=x; 21 for ( int i=1;i<=n;i++ ) L[i]=map[l[i]],R[i]=map[r[i]+1]-1; 22 g[0][0]=1; 23 for ( int i=1;i<=n;i++ ) for ( int j=L[i];j<=R[i];j++ ) 24 { 25 for ( int k=0;k<i;k++ ) 26 { 27 bool flag=true; 28 for ( int p=k+1;p<=i;p++ ) flag&=(L[p]<=j and j<=R[p]); 29 if ( !flag ) continue; 30 int t=i-k; 31 long long pL=val[j],pR=val[j+1]-1,cnt=C(pR-pL+t,t); 32 long long res=(pL+pR)%mod*t%mod*inv2%mod*cnt%mod; 33 for ( int l=0;l<j;l++ ) (f[i][j]+=cnt*f[k][l]+g[k][l]*res)%=mod,(g[i][j]+=cnt*g[k][l])%=mod; 34 } 35 } 36 for ( int i=L[n];i<=R[n];i++ ) (ans+=f[n][i])%=mod; 37 return !printf("%lld ",ans); 38 }