sgu 481 / gym 100671 h Hero of Our Time
求 \(n\) 个点带标号的基环树个数 . 没有模数 .
\(3\leq n\leq 5000\)
第一步肯定是枚举环，考虑环的长度为 \(i\) . 长度为 \(i\) 的环的方案书为 \(g(i)\) .
那么，不同的环的种类就是 \(\dbinom{n}{i}\frac{i!}{2i}=\dbinom{n}{i}\frac{(i-1)!}{2}\) .
接下来考虑 \(n\) 个点，\(k\) 个有根树的方案书 ，为 \(f(n,i)\) .
\[g(i)=f(n,i)\frac{(i-1)!}{2} \]但是，想了很久很久都发现这个 \(f(n,k)\) 除了 \(dp\) 之外好像没有别的方法，但是此题需要高精度，这样肯定是不可以的 .
很显然知道了有根树的大小可以对 \(k\) 个有根树依次 prufer 序列 . 但是，不能统一 prufer 序列，非常难受 .
但是，如果把环看作一个连通块，那么，此时就是需要将 \(n-i+1\) 个联通块连成一棵无根树 . 这样就可以一起 prufer 序列了.
这个东西在 oi wiki 的 prufer 序列上有，最后的方案书是
\[n^{k-2}\prod s_i \]此时可以得到，对于长度为 \(i\) 的环，方案数是
\[\begin{align} g(i)&=\frac{1}{2}n^{n-i+1-2}\dbinom{n}{i}i(i-1)!\\ &=\frac{1}{2}n^{n-i-1}\dbinom{n}{i} i!\\ &=\frac{1}{2}n^{n-i-1}\frac{n!}{i!(n-i)!}i!\\ &=\frac{1}{2}n^{n-i-1}\frac{n!}{(n-i)!}\\ &=\frac{1}{2}n^{n-i-1}n^{\underline{i}} \end{align} \]答案即为 \(\sum g(i)\) .
需要高精度，这个式子已经很简短了，开 \(2n\) 个bignumber 存储 \(n^{\underline{i}}\) 和 \(n^i\) 是会爆空间的 .
考虑每次直接乘上 \((n-i)\) 除以 \(n\) .
最后再除以 \(2\) .
不能用 vector 维护 bignumber，只能用数组，但是还是被卡常数了，需要1600ms .
考虑高精度 \(9\) 位一压 .
但此时就遇到了一些问题，输出的时候直接 cout 输出不了前导 \(0\) .
时间复杂度 : \(O(n^2)\)
空间复杂度 : \(O(n)\)
code
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include
using namespace std;
const int mod=1e9;
class BigNumber{
public:
int len,v[10000];
void init(){len=0;}
};
inline void print(BigNumber a);
BigNumber operator+(const BigNumber&a,const BigNumber&b){
BigNumber res;res.init();
long long tmp=0;
for(int i=0;i=0;i--){
tmp=1ll*tmp*mod+a.v[i];
res.v[res.len++]=tmp/b;
tmp%=b;
}
reverse(res.v,res.v+res.len);
while(res.v[res.len-1]==0)res.len--;
return res;
}
inline void print(BigNumber a){
cout<=0;i--){
int tmp[9];
for(int j=0;j<9;j++){
tmp[j]=a.v[i]%10;
a.v[i]/=10;
}
for(int j=8;j>=0;j--)cout<>n;
x.init();
x.v[x.len++]=1;
for(int i=1;i<=2;i++)x=x*(n-i+1);
for(int i=1;i<=n-3;i++)x=x*n;
BigNumber res;
for(int i=3;i<=n;i++){
x=x*(n-i+1)/n;
res=res+x;
}
print(res/2);
return 0;
}
/*inline? ll or int? size? min max?*/