无聊的水题。
无聊的水题 I
DLS 喜欢上树。
但是他并不想把一道数据结构题出到树上，他喜欢计 Tree。这一天，他想自己造一棵树，他手头有 \(N\) 个树的节点，标号为 \(1 \sim N\)，他会在它们之间连边，我们定义两颗树不同，当且仅当一对节点在一棵树中有连边，另一棵树中没有连边。
但他不喜欢一棵太多分叉的树，于是他想让这棵树的节点中最大的度数为 \(M\)。DLS 由于不太擅长理科，所以希望你帮他计算有多少棵这样的树。
答案对 \(998244353\) 取模。
题如其名。
差分一下，最大恰好转换为每个数不超过。
Prufer 序列，每一个点的出现次数都小于 \(M\) 的方案数。
\(n - 2\) 个点，每个点的出现次数都小于 \(m\)。
统计 \(cnt\) 数组。
\[(n - 2)! [n - 2] \left( \sum_{i = 0} ^m \frac {x^i}{i!} \right) ^ n \]是不是做完了。
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
namespace azus{
using namespace Poly;
int n;
int jc[2000005], inv[2000005];
int calc(int m){
poly a;
for(int i = 0; i <= m; i ++)
a.push_back(inv[i]);
a.resize(n);
// polyOutput(a);
a = polyPow(a, n);
// polyOutput(a);
return jc[n - 2] * a[n - 2] % P;
}
int main(){
jc[0] = inv[0] = 1;
for(int i = 1; i <= 2000000; i ++)
jc[i] = jc[i - 1] * i % P;
inv[2000000] = Ksm(jc[2000000], P - 2);
for(int i = 1999999; i >= 1; i --)
inv[i] = inv[i + 1] * (i + 1) % P;
int m;
cin >> n >> m;
cout << (P + calc(m - 1) - calc(m - 2)) % P;
return 0;
}
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
int T = 1;
while(T --) azus::main();
return 0;
}