解：讲一个别的题解里我比较难以理解的地方，就是为什么可以把这两个东西合起来看成某一个连通块指数是2m而别的指数都是m。
其实很好理解，但是别人都略过了......把后面的∑提到∏的前面，然后展开，也可以理解成把∏塞到∑里面。
然后我们就发现对于每个生成树，我们其实有n种选择，分别把某个块的次数变成2m，且每种选择都作为一棵生成树计入贡献，且这回的贡献，一个树内部各个块全部是乘积的形式。
发现贡献与度数有关，又要求所有生成树，于是考虑prufer序列。
如何看待每个点是一个连通块？就是对于一种生成树，实际方案要乘上(点数度数)。代表每条边连哪个点。
这样一个生成树的权值是这个东西：
接下来考虑钦定每个连通块的度数。在prufer序列中每个数的出现次数是度数-1，于是令di = di - 1
首先要把这些点在prufer中排列一下，于是有：
接下来一顿操作，把di！塞到∏里面，(n-2)!提出来，就有个式子。
然后考虑生成函数，推荐这个。
关于求等幂和这个式子，实在是不理解...
这东西还要我用vector写多项式......
然后搞来搞去，不管了...
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector> typedef long long LL;
const int N = ;
const LL MO = , G = ;
typedef LL arr[N << ];
typedef std::vector<LL> Poly; arr A, B, exp_t, inv_t, inv_t2, f, g, h, p, ex;
int r[N << ], n;
LL m, a[N], pw[N]; inline LL qpow(LL a, LL b) {
a %= MO;
LL ans = ;
while(b) {
if(b & ) ans = ans * a % MO;
a = a * a % MO;
b = b >> ;
}
return ans;
} inline void prework(int n) {
static int R = ;
if(R == n) return;
R = n;
int lm = ;
while(( << lm) < n) lm++;
for(int i = ; i < n; i++) r[i] = (r[i >> ] >> ) | ((i & ) << (lm - ));
return;
} inline void NTT(LL *a, int n, int f) {
prework(n);
for(int i = ; i < n; i++) {
if(i < r[i]) std::swap(a[i], a[r[i]]);
}
for(int len = ; len < n; len <<= ) {
LL Wn = qpow(G, (MO - ) / (len << ));
if(f == -) Wn = qpow(Wn, MO - );
for(int i = ; i < n; i += (len << )) {
LL w = ;
for(int j = ; j < len; j++) {
LL t = a[i + len + j] * w % MO;
a[i + len + j] = (a[i + j] - t) % MO;
a[i + j] = (a[i + j] + t) % MO;
w = w * Wn % MO;
}
}
}
if(f == -) {
LL inv = qpow(n, MO - );
for(int i = ; i < n; i++) a[i] = a[i] * inv % MO;
}
return;
} inline void mul(const LL *a, const LL *b, LL *c, int n) {
int len = ;
while(len < n + n) len <<= ;
memcpy(A, a, n * sizeof(LL)); memset(A + n, , (len - n) * sizeof(LL));
memcpy(B, b, n * sizeof(LL)); memset(B + n, , (len - n) * sizeof(LL));
NTT(A, len, ); NTT(B, len, );
for(int i = ; i < len; i++) c[i] = A[i] * B[i] % MO;
NTT(c, len, -);
memset(c + n, , (len - n) * sizeof(LL));
return;
} inline Poly mul(const Poly &a, const Poly &b) {
int len = , lena = a.size(), lenb = b.size();
while(len < lena + lenb) len <<= ;
Poly ans(lena + lenb - );
for(int i = ; i < lena; i++) A[i] = a[i];
for(int i = ; i < lenb; i++) B[i] = b[i];
memset(A + lena, , (len - lena) * sizeof(LL));
memset(B + lenb, , (len - lenb) * sizeof(LL));
NTT(A, len, ); NTT(B, len, );
for(int i = ; i < len; i++) A[i] = A[i] * B[i] % MO;
NTT(A, len, -);
for(int i = ; i < lena + lenb - ; i++) ans[i] = A[i];
return ans;
} void Inv(const LL *a, LL *b, int n) {
if(n == ) {
b[] = qpow(a[], MO - );
b[] = ;
return;
}
Inv(a, b, n >> );
/// ans = b * (2 - a * b);
memcpy(A, a, n * sizeof(LL)); memset(A + n, , n * sizeof(LL));
memcpy(B, b, n * sizeof(LL)); memset(B + n, , n * sizeof(LL));
NTT(A, n << , ); NTT(B, n << , );
for(int i = ; i < (n << ); i++) b[i] = B[i] * ( - A[i] * B[i] % MO) % MO;
NTT(b, n << , -);
memset(b + n, , n * sizeof(LL));
return;
} inline void getInv(const LL *a, LL *b, int n) {
int len = ;
while(len < n) len <<= ;
Inv(a, b, len);
memset(b + n, , (len - n) * sizeof(LL));
return;
} inline Poly getInv(const Poly &a) {
int n = a.size(), len = ;
while(len < n) len <<= ;
for(int i = ; i < n; i++) inv_t[i] = a[i];
memset(inv_t + n, , (len - n) * sizeof(LL));
getInv(inv_t, inv_t2, n);
Poly ans(n);
for(int i = ; i < n; i++) ans[i] = inv_t2[i];
return ans;
} inline void der(const LL *a, LL *b, int n) {
for(int i = ; i < n - ; i++) {
b[i] = a[i + ] * (i + ) % MO;
}
b[n - ] = ;
return;
} inline void ter(const LL *a, LL *b, int n) {
for(int i = n - ; i >= ; i--) {
b[i] = a[i - ] * qpow(i, MO - ) % MO;
}
b[] = ;
return;
} inline void getLn(const LL *a, LL *b, int n) {
getInv(a, inv_t, n);
der(a, A, n);
int len = ;
while(len < n + n) len <<= ;
memset(A + n, , (len - n) * sizeof(LL));
memcpy(B, inv_t, n * sizeof(LL)); memset(B + n, , (len - n) * sizeof(LL));
NTT(A, len, ); NTT(B, len, );
for(int i = ; i < len; i++) b[i] = A[i] * B[i] % MO;
NTT(b, len, -);
memset(b + n, , (len - n) * sizeof(LL));
ter(b, b, n);
return;
} void Exp(const LL *a, LL *b, int n) {
if(n == ) {
b[] = ;
b[] = ;
return;
}
Exp(a, b, n >> );
/// ans = b * (1 + a - ln b)
getLn(b, exp_t, n);
for(int i = ; i < n; i++) A[i] = (a[i] - exp_t[i]) % MO;
A[] = (A[] + ) % MO;
memset(A + n, , n * sizeof(LL));
memcpy(B, b, n * sizeof(LL)); memset(B + n, , n * sizeof(LL));
NTT(A, n << , ); NTT(B, n << , );
for(int i = ; i < (n << ); i++) b[i] = A[i] * B[i] % MO;
NTT(b, n << , -);
memset(b + n, , n * sizeof(LL));
return;
} inline void getExp(const LL *a, LL *b, int n) {
int len = ;
while(len < n) len <<= ;
Exp(a, b, len);
memset(b + n, , (len - n) * sizeof(LL));
return;
} inline void out(const Poly &a) {
//printf("siz = %d ", a.size());
for(int i = ; i < a.size(); i++) {
printf("%lld ", (a[i] + MO) % MO);
}
printf("\n");
return;
} Poly dvd(int l, int r) {
if(l == r) {
Poly res();
res[] = ; res[] = -a[r];
return res;
}
int mid = (l + r) >> ;
Poly ans = mul(dvd(l, mid), dvd(mid + , r));
return ans;
} inline void solve1() {
Poly q = dvd(, n);
Poly p(n);
for(int i = ; i < n; i++) {
p[i] = q[i] * (n - i) % MO;
}
p = mul(p, getInv(q));
for(int i = ; i < n; i++) {
ex[i] = p[i];
//printf("ex %d = %lld \n", i, ex[i]);
}
return;
} int main() { scanf("%d%lld", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
}
///
solve1(); pw[] = ;
for(int i = ; i <= n; i++) pw[i] = pw[i - ] * i % MO;
for(int i = ; i < n; i++) {
f[i] = qpow(i + , m) * qpow(pw[i], MO - ) % MO;
h[i] = qpow(i + , m << ) * qpow(pw[i], MO - ) % MO;
}
getInv(f, p, n);
mul(p, h, h, n); getLn(f, g, n);
for(int i = ; i < n; i++) {
g[i] = g[i] * ex[i] % MO;
h[i] = h[i] * ex[i] % MO;
}
getExp(g, f, n); mul(h, f, f, n); LL ans = f[n - ];
for(int i = ; i < n - ; i++) ans = ans * i % MO;
for(int i = ; i <= n; i++) ans = ans * a[i] % MO; if(ans < ) ans += MO;
printf("%lld\n", ans); return ;
}
AC代码