LOJ2983. 「WC2019」数树
task0
有(i)条边一样答案就是(y^{n - i})
task1
这里有个避免容斥的方法，如果有(i)条边重复我们要算的是(y^{n - i})，设(a = y^{-1})那么我们可以对于选了i条边的方案算(a^{i})
可是这样需要容斥，所以有个神奇的技巧
((a - 1 + 1)^{i} = sum_{j = 0}^{i}(a - 1)^{j}inom{i}{j})
这样，对于至少选了(j)条边的方案，每选一条边乘上一个((a - 1))就可以避免容斥了（以下设(z = a - 1))
分成(m)个联通块方案数是
(n^{m - 2}prod_{i = 1}^{m}a_{i})
这相当于断开一条边乘一下N，且每个联通块要选出一个点，dp完了之后答案再乘上(N^{-1})
就直接设(dp[i][0/1])表示(i)所在的联通块是否选了一个点的方案数
task2
还是上面那个技巧，然后要爆推式子，假如硬点(i)条边被选了的有(f_{i})棵树
(sum_{i = 1}^{N - 1}f_iz^{i})
[f_{i} = frac{N!}{prod_{k = 1}^{M}a_{k}!} frac{1}{(N - x)!} prod_{i = k}^{M}a_{k}^{a_{k} - 2} (n^{n - x - 2} prod_{k = 1}^{M}a_{k})^{2}
]
从左到右分别是
给每个联通块分配点，消除联通块的顺序，联通块内生成树的个数，联通块形成的树的个数
有点乱，给合一下就是
[f_{i} = N! prod_{k = 1}^{M}frac{a_{k}^{a_{k}}}{a_{k}!} frac{n^{2(n - x - 2)}}{(N - x)!}
]
然后我们把答案带进去
[ans = N!sum_{i = 1}^{N} frac{Z^{N - i}n^{2i - 4}}{i!}prod_{k = 1}^{M}frac{a_{k}^{a_{k}}}{a_{k}!}
]
我们给(a_{k})设个生成函数，去掉和i无关的项就是
[ans = N!frac{Z^{N}}{n^{4}}sum_{i = 1}^{N}frac{frac{n^{2i}}{Z^{i}}prod_{k = 1}^{M}frac{a_{k}^{a_{k}}x^{a_{k}}}{a_{k}!} }{i!}
]
因为(M = i)
所以也可以写成
[ans = N!frac{Z^{N}}{n^{4}}sum_{i = 1}^{N}frac{[x^{n}](frac{n^{2}}{Z}frac{a_{k}^{a_{k}}x^{a_{k}}}{a_{k}!})^{i} }{i!}
]
于是设(F(x) = sum_{i = 1}^{infty} frac{n^{2}}{Z}frac{i^{i}}{i!}x^{i})
很容易知道上面后半部分的式子是(e^{F(x)})，然后乘上前面的系数就做完了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 100005
#define ba 47
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 998244353,MAXL = (1 << 20);
int N,Y,op,W[MAXL + 5];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
void update(int &x,int y) {
x = inc(x,y);
}
int fpow(int x,int c) {
int res = 1,t = x;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
namespace task0 {
bool vis[MAXN];
map<pii,int> zz;
void Main() {
int a,b;
for(int i = 1 ; i < N ; ++i) {
read(a);read(b);
if(a > b) swap(a,b);
zz[mp(a,b)] = 1;
}
int ans = fpow(Y,N);
int t = fpow(Y,MOD - 2);
for(int i = 1 ; i < N ; ++i) {
read(a);read(b);
if(a > b) swap(a,b);
if(zz[mp(a,b)]) ans = mul(ans,t);
}
out(ans);enter;
}
}
namespace task1 {
struct node {
int to,next;
}E[MAXN * 2];
int head[MAXN],sumE,Z;
int dp[MAXN][2],tmp[2];
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
void dfs(int u,int fa) {
dp[u][0] = 1,dp[u][1] = 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa) {
dfs(v,u);
tmp[0] = tmp[1] = 0;
update(tmp[1],mul(mul(dp[u][1],dp[v][1]),N));
update(tmp[1],mul(mul(dp[u][1],dp[v][0]),Z));
update(tmp[0],mul(mul(dp[u][0],dp[v][0]),Z));
update(tmp[0],mul(mul(dp[u][0],dp[v][1]),N));
update(tmp[1],mul(mul(dp[u][0],dp[v][1]),Z));
dp[u][0] = tmp[0];dp[u][1] = tmp[1];
}
}
}
void Main() {
int a,b;
for(int i = 1 ; i < N ; ++i) {read(a);read(b);add(a,b);add(b,a);}
Z = fpow(Y,MOD - 2);Z = inc(Z,MOD - 1);
dfs(1,0);
int ans = dp[1][1];
ans = mul(ans,fpow(N,MOD - 2));ans = mul(ans,fpow(Y,N));
out(ans);enter;
}
}
namespace task2 {
int fac[MAXN],invfac[MAXN],inv[MAXN];
vector<int> f,g;
void NTT(vector<int> &p,int L,int on) {
p.resize(L);
for(int i = 1,j = L >> 1; i < L - 1 ; ++i) {
if(i < j) swap(p[i],p[j]);
int k = L >> 1;
while(j >= k) {
j -= k;
k >>= 1;
}
j += k;
}
for(int h = 2 ; h <= L ; h <<= 1) {
int wn = W[(MAXL + on * MAXL / h) % MAXL];
for(int k = 0 ; k < L ; k += h) {
int w = 1;
for(int j = k ; j < k + h / 2 ; ++j) {
int u = p[j],t = mul(w,p[j + h / 2]);
p[j] = inc(u,t);
p[j + h / 2] = inc(u,MOD - t);
w = mul(w,wn);
}
}
}
if(on == -1) {
int invL = fpow(L,MOD - 2);
for(int i = 0 ; i < L ; ++i) p[i] = mul(p[i],invL);
}
}
void limit(vector<int> &p,int N) {
if(p.size() > N) p.resize(N);
}
vector<int> operator * (vector<int> a,vector<int> b) {
int t = a.size() + b.size() - 2;
int L = 1;
while(L <= t) L <<= 1;
NTT(a,L,1);NTT(b,L,1);
vector<int> c;c.resize(L);
for(int i = 0 ; i < L ; ++i) c[i] = mul(a[i],b[i]);
NTT(c,L,-1);
return c;
}
vector<int> Derivative(vector<int> p) {
vector<int> res(p.size() - 1);
for(int i = 0 ; i < p.size() - 1 ; ++i) {
res[i] = mul(p[i + 1],i + 1);
}
if(res.size() == 0) res.pb(0);
return res;
}
vector<int> Integral(vector<int> p) {
vector<int> res(p.size() + 1);
for(int i = 1 ; i <= p.size() ; ++i) {
res[i] = mul(p[i - 1],inv[i]);
}
return res;
}
vector<int> inverse(vector<int> p,int len) {
vector<int> g;
if(len == 1) {
g.pb(fpow(p[0],MOD - 2));
return g;
}
g = inverse(p,len >> 1);
int t = p.size() - 1 + 2 * (g.size() - 1);
int L = 1;
while(L <= t) L <<= 1;
NTT(p,L,1);NTT(g,L,1);
for(int i = 0 ; i < L ; ++i) {
g[i] = inc(mul(2,g[i]),MOD - mul(mul(g[i],g[i]),p[i]));
}
NTT(g,L,-1);
g.resize(len);
return g;
}
vector<int> Inverse(vector<int> p) {
int L = 1,t = p.size() - 1;
while(L <= t) L <<= 1;
return inverse(p,L);
}
vector<int> ln(vector<int> p) {
int t = p.size();
vector<int> g = Inverse(p) * Derivative(p);
g = Integral(g);limit(g,t);
return g;
}
vector<int> exp(vector<int> p,int len) {
vector<int> g,f;
if(len == 1) {
g.pb(1);return g;
}
g = exp(p,len >> 1);
p.resize(len);
f = g;f.resize(len);
f = ln(f);
int L = 1,t = len + g.size() - 1;
while(L <= t) L <<= 1;
NTT(p,L,1);NTT(f,L,1);NTT(g,L,1);
for(int i = 0 ; i < L ; ++i) {
g[i] = inc(g[i],mul(g[i],inc(p[i],MOD - f[i])));
}
NTT(g,L,-1);
limit(g,len);
return g;
}
vector<int> Exp(vector<int> p) {
int L = 1,t = p.size() - 1;
while(L <= t) L <<= 1;
return exp(p,L);
}
void Print(vector<int> c) {
for(int i = 0 ; i < c.size() ; ++i) {
out(c[i]);space;
}
enter;
}
void Main() {
if(Y == 1) {
out(fpow(N,2 * N - 4));enter;return;
}
int Z = fpow(Y,MOD - 2);Z = inc(Z,MOD - 1);
fac[0] = 1;
for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);
invfac[N] = fpow(fac[N],MOD - 2);
for(int i = N - 1 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);
inv[1] = 1;
for(int i = 2 ; i <= N ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);
int t = N,l = 1;
while(l <= t) l <<= 1;
f.resize(l);
int invZ = fpow(Z,MOD - 2);
for(int i = 1 ; i <= N ; ++i) {
f[i] = mul(N,N);
f[i] = mul(f[i],invZ);
f[i] = mul(f[i],fpow(i,i));f[i] = mul(f[i],invfac[i]);
}
W[0] = 1,W[1] = fpow(3,(MOD - 1) / MAXL);
for(int i = 2 ; i < MAXL ; ++i) {
W[i] = mul(W[i - 1],W[1]);
}
vector<int> a(3),b(3);
g = Exp(f);
int ans = g[N];
ans = mul(ans,fpow(Z,N));
ans = mul(ans,fpow(fpow(N,MOD - 2),4));
ans = mul(ans,fac[N]);
ans = mul(ans,fpow(Y,N));
out(ans);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
read(N);read(Y);read(op);
if(op == 0) task0::Main();
else if(op == 1) task1::Main();
else if(op == 2) task2::Main();
return 0;
}