<span>牛客练习赛 74 F</span>
题目链接
CCA的树
关于树的组合计数
考虑容斥,容易知道总方案数为\(n^{n-2}*m^n\)
考虑在什么情况下不存在好链,容易知道当且仅当不同的颜色组成不同的连通块时,
该种方案下不存在好链
对于每一种固定的方案,我们枚举\(i\)条要断的边
这样会形成\(i+1\)个连通块,有\(C(n-1,i)\)种方案,然后考虑对这\(i+1\)个连通块染色
有\(C(m,i+1)*(i+1)!\)种方案,两个式子相乘即为该形态下方案数
容易知道n个节点每个形态下的方案数相同,期望可消去\(n^{n-2}\)从而得到答案
代码:
#include <bits/stdc++.h>
#define LL long long
#define mod 1023694381
const int N = 1e7 + 101;
using namespace std;
LL fac[N], inv[N];
int n, m, maxn;
LL ksm(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 a,LL b)
{
return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int main()
{
scanf("%d%d",&n,&m);maxn = max(n,m);
fac[0] = 1;
for(int i = 1;i <= maxn; i++) fac[i] = fac[i - 1] * (LL) i % mod;
inv[maxn] = ksm(fac[maxn],mod - 2);
for(int i = maxn - 1;i >= 0; i--) inv[i] = inv[i + 1] * (LL) (i + 1) % mod;
LL ans = ksm(m,n);
for(int i = 0;i <= n - 1; i++)
{
if(i + 1 > m) continue;
ans = (ans - C(n - 1,i) * C(m,i + 1) % mod * fac[i + 1] % mod + mod) % mod;
}
cout << ans << endl;
}