Description
Solution
O(n^4)
- 直接放弃思考矩阵树即可过
n
<
=
80
n<=80
n<=80，获得23分。
O(n^2)
- 考虑先枚举一些特殊边，将n个点分成m个联通块，再用prufer序列计算这个完全图的方案数：
n
m
−
2
∏
i
=
1
m
s
i
n^{m-2}\prod_{i=1}^ms_i
nm−2∏i=1msi
- 考虑prufer序列中的一个值代表了一条边，且长度为
m
−
2
m-2
m−2，那么连边的时候就可以有n个顶点，即
n
m
−
2
n^{m-2}
nm−2。又因为prufer序列出现次数为度数-1，所以每一个联通块只考虑到了度数-1次顶点的选择，所以还有
s
i
si
si的贡献没有计算到。
- 直接DP即可O(n^2)
O(nlogn)
-
∑
s
∏
i
=
1
m
s
i
=
(
∑
i
>
=
0
i
x
i
)
m
[
x
n
]
=
(
x
(
1
−
x
)
2
)
m
[
x
n
]
=
1
(
1
−
x
)
2
m
[
x
n
−
m
]
=
(
1
+
x
+
x
2
+
x
3
+
.
.
.
)
2
m
[
x
n
−
m
]
=
C
n
−
m
+
2
m
−
1
2
m
−
1
=
C
n
+
m
−
1
2
m
−
1
\sum_{s}\prod_{i=1}^ms_i=(\sum_{i>=0}ix^i)^m[x^n]=(\frac{x}{(1-x)^2})^m[x^n]=\frac{1}{(1-x)^{2m}}[x^{n-m}]=(1+x+x^2+x^3+...)^{2m}[x^{n-m}]=C_{n-m+2m-1}^{2m-1}=C_{n+m-1}^{2m-1}
∑s∏i=1msi=(∑i>=0ixi)m[xn]=((1−x)2x)m[xn]=(1−x)2m1[xn−m]=(1+x+x2+x3+...)2m[xn−m]=Cn−m+2m−12m−1=Cn+m−12m−1
- 因此确定m个联通快的方案数就是上面的东西乘上
n
m
−
2
n^{m-2}
nm−2。
- 但是这是至少
n
−
m
n-m
n−m条特殊边的方案数,设至少n条方案为
f
(
n
)
f(n)
f(n)，则答案要求的恰好
g
(
n
)
g(n)
g(n)，有
f
(
n
)
=
∑
m
>
=
n
C
m
n
∗
g
(
m
)
f(n)=\sum_{m>=n}C_m^n*g(m)
f(n)=∑m>=nCmn∗g(m).
- 则
g
(
n
)
=
∑
m
>
=
n
C
m
n
(
−
1
)
m
−
n
f
(
m
)
g(n)=\sum_{m>=n}C_{m}^{n}(-1)^{m-n}f(m)
g(n)=∑m>=nCmn(−1)m−nf(m)，卷积即可求出对应位置的答案。
O(n)
- 我们先考虑
2
x
2^x
2x为权值怎么办，那么相当于任意一个恰好x条的都会被它的任意一个子集算一次，答案实际上就是
∑
f
(
i
)
\sum f(i)
∑f(i)。
- 再考虑权值为
x
2
x
x2^x
x2x怎么做，
x
2
x
=
2
∗
x
2
x
−
1
x2^x=2*x2^{x-1}
x2x=2∗x2x−1，后者就是
2
∗
∑
i
=
0
x
i
C
x
i
2*\sum_{i=0}^xiC_x^i
2∗∑i=0xiCxi。
- 原本计算
2
x
2^x
2x时，是
∑
i
=
0
x
C
x
i
\sum_{i=0}^xC_x^i
∑i=0xCxi，那么现在这个答案显然就是
2
∗
∑
f
(
i
)
∗
i
2*\sum f(i)*i
2∗∑f(i)∗i
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define mo 998244353
#define maxn 1000005
using namespace std;
int n,i;
ll fct[maxn],invf[maxn],ans,f[maxn],mul[maxn];
ll ksm(ll x,ll y){
ll s=1;
for(;y;y/=2,x=x*x%mo) if (y&1)
s=s*x%mo;
return s;
}
ll C(int n,int m){return fct[n]*invf[n-m]%mo*invf[m]%mo;}
int main(){
scanf("%d",&n);
fct[0]=1;for(i=1;i<=2*n;i++) fct[i]=fct[i-1]*i%mo;
invf[2*n]=ksm(fct[2*n],mo-2);
for(i=2*n-1;i>=0;i--) invf[i]=invf[i+1]*(i+1)%mo;
mul[0]=1;for(i=1;i<=n;i++) mul[i]=mul[i-1]*n%mo;
f[n-1]=1;for(i=2;i<=n;i++) f[n-i]=C(n+i-1,2*i-1)*mul[i-2]%mo;
for(i=0;i<n;i++) ans+=f[i]*i%mo;
printf("%lld",ans*2%mo);
}