做多项式把自己做成若只了。
[ABC303Ex] Constrained Tree Degree
给定一个长度为 \(K\) 的正整数序列 \(S\)，求有多少个不同的树 \(T\) 使得：
- \(T\) 中有 \(N\) 个节点。
- 对于 \(T\) 中的任意一个节点 \(i\) 的度数 \(d_i\)，有 \(d_i\in S\)。
无根树计数，考虑 Prufer 序列。
问题转化成，现在有 \(n - 2\) 个数，每个数都是 \([1, n]\) 的整数，且每个数出现的次数加上 \(1\) 一定要在 \(S\) 集合中。那我们先将 \(S\) 集合的所有数减一，之后对 \(S\) 集合的描述默认已经减去 \(1\) 了。
先对每个数出现次数计数，即取 \(n\) 个数和为 \(n - 2\) 的方案数，即：
\[\left[x^{n - 2}\right]\left(\sum x^{s_i}\right)^n \]假设取的数分别是 \(\{a_1, \dots, a_n\}\)，其中 \(a_i \in S\)，那么会乘上一个多重排列，即：
\[\frac{(n - 2)!}{\prod a_i!} \]那么 \((n - 2)!\) 与选择的数无关可以提出来，剩下的阶乘挂到上面的 \(x^{s_i}\) 下面去。
所以最后的式子是：
\[(n-2)! \times \left[x^{n - 2}\right]\left(\sum\frac{x^{s_i}}{s_i!}\right)^n \]#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
namespace Poly{
using poly = vector<int>;
const int G = 3, P = 998244353;
const int inv2 = 499122177;
int Ksm(int u, int v){
int ret = 1;
while(v){
if(v & 1) ret = 1ll * ret * u % P;
u = 1ll * u * u % P, v >>= 1;
}
return ret;
}
int NTT(poly &A, int N){
int d = N >> 1;
poly trn;
trn.push_back(0);
trn.push_back(d);
for(int w = 2; w <= N; w <<= 1){
d >>= 1;
for(int c = 0; c < w; c ++)
trn.push_back(trn[c] | d);
}
for(int i = 1; i < N; i ++)
if(trn[i] > i)
swap(A[i], A[trn[i]]);
for(int len = 2, M = 1; len <= N; M = len, len <<= 1){
int W;
W = Ksm(G, (P - 1) / len);
for(int l = 0; l <= N - len + 1; l += len){
auto w0 = 1;
for(int nw = l; nw < l + M; nw ++){
int x = A[nw], y = 1ll * w0 * A[nw + M] % P;
A[nw] = (x + y) % P, A[nw + M] = (x - y + P) % P;
w0 = 1ll * w0 * W % P;
}
}
}
return 0;
}
poly convolution(poly a, poly b){
int n = a.size(), m = b.size();
if(!n || !m)
return {};
int sm = n + m - 1;
int k = 1;
while(k < sm)
k <<= 1;
a.resize(k), b.resize(k);
NTT(a, k);
NTT(b, k);
for(int i = 0; i < k; i ++)
a[i] = 1ll * a[i] * b[i] % P;
NTT(a, k);
reverse(++ a.begin(), a.end());
int invk = Ksm(k, P - 2);
for(int i = 0; i < a.size(); i ++)
a[i] = 1ll * a[i] * invk % P;
a.resize(n + m - 1);
return a;
}
poly polyInv(poly f){
int n = f.size();
int k = 1;
while(k < n)
k <<= 1;
k <<= 1;
poly g;
f.resize(k);
g.push_back(Ksm(f[0], P - 2));
for(int len = 2; len <= k; len <<= 1){
int M = len >> 1;
poly tmp2, tmp1;
for(int i = 0; i < M; i ++)
tmp2.push_back(g[i]);
for(int i = 0; i < M; i ++)
tmp1.push_back(f[i]);
tmp1.resize(len);
tmp2 = convolution(tmp2, tmp2);
tmp2 = convolution(tmp1, tmp2);
for(int i = 0; i < M; i ++)
g[i] = (2ll * g[i] % P + P - tmp2[i]) % P;
for(int i = M; i < len; i ++)
g.push_back((2ll * g[i] % P + P - tmp2[i]) % P);
}
g.resize(n);
return g;
}
poly polyDev(poly f){
poly g;
int k = f.size();
for(int i = 1; i < k; i ++)
g.push_back(1ll * i * f[i] % P);
g.resize(k - 1);
return g;
}
poly polyInDev(poly f){
poly g;
int k = f.size();
g.push_back(0);
for(int i = 1; i < k; i ++)
g.push_back(1ll * f[i - 1] * Ksm(i, P - 2) % P);
return g;
}
poly polyLn(poly a){
int n = a.size();
poly b = a;
a = polyDev(a);
b = polyInv(b);
a = convolution(a, b);
a = polyInDev(a);
a.resize(n);
return a;
}
int polyOutput(poly a){
for(int i = 0; i < a.size(); i ++)
cout << a[i] << " ";
cout << "\n";
return 0;
}
poly polyExp(poly f){
int n = f.size();
int k = 1;
while(k < n)
k <<= 1;
k <<= 1;
poly g;
f.resize(k);
g.push_back(1);
for(int len = 2; len <= k; len <<= 1){
int M = len >> 1;
poly tmp2;
for(int i = 0; i < M; i ++)
tmp2.push_back(g[i]);
auto tmp3 = polyLn(tmp2);
for(int i = 0; i < M; i ++)
tmp3[i] = (((P - tmp3[i] + f[i]) % P) + P) % P;
tmp3[0] ++;
tmp3[0] %= P;
tmp2 = convolution(tmp3, tmp2);
for(int i = 0; i < M; i ++)
g[i] = tmp2[i];
for(int i = M; i < len; i ++)
g.push_back(tmp2[i]);
}
g.resize(n);
return g;
}
poly polyPow(poly a, int k){
int n = a.size();
int t = 0;
for(int i = 0; i < n; i ++){
if(a[t] != 0) break;
t ++;
}
if(t == n) return a;
int r = Ksm(a[t], P - 2);
poly b;
for(int i = t; i < n; i ++)
b.push_back(1ll * a[i] * r % P);
a.resize(t);
int m = b.size();
b = polyLn(b);
for(int i = 0; i < m; i ++)
b[i] = 1ll * b[i] * k % P;
b = polyExp(b);
for(int i = 0; i < m; i ++)
a.push_back(b[i]);
return a;
}
}
namespace azus{
using namespace Poly;
int n, m;
poly a;
int jc[200005], inv[200005];
int main(){
cin >> n >> m;
a.resize(n);
jc[0] = inv[0] = 1;
for(int i = 1; i <= n; i ++)
jc[i] = jc[i - 1] * i % P;
inv[n] = Ksm(jc[n], P - 2);
for(int i = n - 1; i >= 1; i --)
inv[i] = inv[i + 1] * (i + 1) % P;
for(int i = 1, x; i <= m; i ++){
cin >> x;
x --;
a[x] = inv[x];
}
if(!a[0]) return cout << 0, 0;
// polyOutput(a);
a = polyPow(a, n);
// polyOutput(a);
cout << a[n - 2] * jc[n - 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;
}
SError_ 薄纱我系列。
标签：我蝶,int,back,poly,++,push,SError,tmp2 From： https://www.cnblogs.com/AzusidNya/p/18231945