（搬的长乐一中的题）

前言

分档暴力分写挂 \(10\) pts 导致排名 \(-2\)。

暴力的艺术，一题不会可以 rk7，此记。

A

Subtask1

\(f_{i,j}\) 表示前 \(i\) 个数或起来为 \(j\) 的方案数。

\(O(nt^2)\)，上矩阵可以 \(O(t^3\log n)\)。

Subtask5

考虑容斥，设 \(S_k\) 表示钦定某 \(k\) 位必定不选，剩下的位可选可不选。

可以知道答案为 \(\displaystyle \sum_{k=0}^m (-1)^k S_k\)。

发现 \(2^k\bmod 3\ne 0\)。

于是将 \(t\) 的二进制下为 \(1\) 的位按模 \(3\) 的结果分为两部分，记余数为 \(i\) 的那一个集合为 \(T_i\)。

设 \(dp_{i,j,k}\) 表示当前至多选 \(i\) 个 \(1\) 位，至多选 \(j\) 个 \(2\) 位，它们的和 \(\bmod 3\) 为 \(k\) 的方案数。

之后对于一对 \(i,j\)，其对 \(S_{|T_1|+|T_2|-i-j}\) 会贡献 \(dp_{i,j,0}^n\times C_{|T_1|}^i\times C_{|T_2|}^j\)。

复杂度 \(O(log n\log ^2 t)\)。

namespace Subtask3 {LL dp[70][70][3],S[70],C[70][70];void solve() {int n1=0,n2=0;ROF(i,61,0) if(t>>i&1) {if((1LL<<i)%3==1) n1++;else n2++;}FOR(i,0,61) C[i][0]=1;FOR(i,1,61) FOR(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mo;dp[0][0][0]=1;FOR(i,0,n1) FOR(j,0,n2) {if(i) FOR(k,0,2) dp[i][j][k]=(dp[i-1][j][k]+dp[i-1][j][(k+2)%3])%Mo;if(j) FOR(k,0,2) dp[i][j][k]=(dp[i][j-1][k]+dp[i][j-1][(k+1)%3])%Mo;}cout<<dp[1][1][0]<<"\n";FOR(i,0,n1) FOR(j,0,n2) (S[n1+n2-i-j]+=1LL*power(dp[i][j][0],n)*C[n1][i]%Mo*C[n2][j]%Mo)%=Mo;LL ans=0,op=1;FOR(i,0,n1+n2) {ans=(ans+Mo+op*S[i])%Mo;op=-op;}cout<<(ans+Mo)%Mo<<"\n";}
}

B

答案就是所有方案中虚树的边权和的 \(2\) 倍减掉虚树直径的和再除以方案数 \(C_m^k\)。

前 \(4\) 个子任务都是白给的。

考虑转为求虚树边权和的和与虚树直径和。

前者枚举每条边，这条边能够贡献给一棵虚树当且仅当砍断这条边后，这棵虚树在两个联通块中都有点，方案是好算的。

后者直接暴力枚举直径点对，考虑钦定直径后哪些关键点满足选了之后直径不变：

假设 \(w\) 可以被选，则：

\(dis(u,v)<dis(u,w)\) 或者 \(dis(u,v)=dis(u,w)\and v<w\)。
\(dis(u,v)<dis(v,w)\) 或者 \(dis(u,v)=dis(v,w)\and u<w\)。

于是虚树的点只可能在这些点的集合中，方案数仍旧好算。

不过 \(m^3\log n\) 可能被卡，需预处理。

\(O(n^2+m^3)\)。

namespace Subtask5 {LL len=0,dim=0;LL Cl[N][N];LL C(int n,int m) {if(n<m||m<0) return 0;return Cl[n][m];}void solve() {FOR(i,0,n) Cl[i][0]=1;FOR(i,1,n) FOR(j,1,i)Cl[i][j]=(Cl[i-1][j-1]+Cl[i-1][j])%Mo;LL inv=power(C(m,k),Mo-2);FOR(i,1,n) for(int j:e[i]) {if(dep[i]>dep[j]) continue;int sz1=m-siz[j],sz2=siz[j];len+=1uLL*(C(m,k)+Mo-C(sz1,k)+Mo-C(sz2,k))%Mo;len%=Mo; }sort(a+1,a+m+1);FOR(i,1,m) FOR(j,i+1,m) {int cnt=0;FOR(z,1,m) {if(z==i||z==j) continue;if((la[a[z]][a[i]]==la[a[i]][a[j]]&&a[z]<a[j])||(a[z]<a[i]&&la[a[z]][a[j]]==la[a[i]][a[j]])) continue;if(la[a[z]][a[i]]>la[a[i]][a[j]]||la[a[z]][a[j]]>la[a[i]][a[j]]) continue;cnt++;}dim=(dim+1LL*C(cnt,k-2)*dis(a[i],a[j])%Mo)%Mo;}cout<<(len*2LL%Mo+Mo-dim)*inv%Mo<<"\n";}
}