CF1824B2
- \(k\) 为奇数时，注意到每次好点移动一格至少会增加 $ \lfloor \frac{k}{2} \rfloor + 1 - \lfloor \frac{k}{2} \rfloor$ 的长度，所以好点个数为 \(1\)。
- \(k\) 为偶数时，注意到好点一定在一条链上，我们计算出有多少条边 \((u,v)\) 满足 \(u\) 和 \(v\) 为好点，答案就是边数 \(+1\)
可以得到，必须两侧的子树大小为 \(\frac{k}{2}\) 时，才能满足
具体的，左侧子树大小为 \(x\) ，右侧子树大小为 \(n-x\)，则方案数为 \(\binom{x}{\frac{k}{2}} \binom{n-x}{\frac{k}{2}}\)
由于算的是期望，答案需除以总方案数，即\(\binom{n}{k}\)。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=200005,mod=1e9+7;
ll fac[N],ifac[N];
int h[N],e[N*2],ne[N*2],idx;
int n,k,s[N];
ll ans;
void add(int u,int v){
e[++idx]=v,ne[idx]=h[u],h[u]=idx;
}
ll poww(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll C(ll n,ll m){
if(n<0||m<0||n<m) return 0;
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void init(int n){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=poww(fac[n],mod-2);
for(int i=n;i;i--) ifac[i-1]=ifac[i]*i%mod;
}
void dfs(int u,int f){
s[u]=1;
for(int i=h[u];i;i=ne[i]){
int j=e[i];
if(j==f) continue;
dfs(j,u);
s[u]+=s[j];
ans=(ans+C(s[j],k>>1)*C(n-s[j],k>>1)%mod)%mod;
}
}
signed main(){
cin>>n>>k;
if(k&1) return cout<<1<<endl,0;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
}
init(n),dfs(1,0);
cout<<(ans*ifac[n]%mod*fac[k]%mod*fac[n-k]%mod+1)%mod;
return 0;
}
ARC163D
考虑分成两个集合 \(A\) 和 \(B\)，满足对于任意的 \(u \in A,v \in B\) 边的方向为 \(u \to v\)。
设 \(f_{i,j,k}\) 为加入了 \(i\) 个 A集合中的点， \(j\) 个 \(B\) 集合中的点， 有 \(k\) 条边满足条件的方案数
转移则考虑第 \(i+1\) 个点
考虑将 \(i + j + 1\) 号点加入到 \(A\) 或 \(B\)，转移如下：
\[f_{i + 1, j, k + x} \gets \binom ixf_{i, j, k} (0 \le x \le i) \]\[\\ f_{i, j + 1, k + i + x} \gets \binom jxf_{i, j, k} (0 \le x \le j)\\ \]-
在 \(A\) 内加入最大点 \(u\)，\(u\) 向 \(B\) 内的连边都是逆向的，向 \(A\) 内的连边任意。钦定 \(x\) 条为正向的，则系数为 \(\binom ix\)。
-
在 \(B\) 内加入最大点 \(u\)，\(u\) 向 \(A\) 内的连边都是正向的，向 \(B\) 内的连边任意。钦定 \(x\) 条为正向的，则系数为 \(\binom jx\)。
时间复杂度 \(O(n^3m)\)。
#include <bits/stdc++.h>
using namespace std;
const int N=31,M=N*N>>1,mod=998244353;
int n,m,C[M][M],f[N][N][M],ans;
int main(){
cin>>n>>m;
C[0][0]=1;
for(int i=1;i<=n*(n-1)/2;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
f[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0,s=i;s<n;j++,s++){
for(int k=0;k<=m;k++){
for(int x=0;x<=i;x++)
f[i+1][j][k+x]=(f[i+1][j][k+x]+1ll*C[i][x]*f[i][j][k])%mod;
for(int x=0;x<=j;x++)
f[i][j+1][k+i+x]=(f[i][j+1][k+i+x]+1ll*C[j][x]*f[i][j][k])%mod;
}
}
}
int ans=mod-C[n*(n-1)/2][m];
for(int i=0,j=n;i<=n;i++,j--) ans=(ans+f[i][j][m])%mod;
cout<<ans<<endl;
return 0;
}