题面
给出一个大小为 $n$ 的无向图，求使得任意两点间只有1～2条简单路径的加边方案数。（$n \leq 20$）。
题解
首先可以知道最终这个图要么是个树，要么是一个树多了一条边（也就是基环树）。
那么我就不会了。。。
后面了解到了 Prufer序列 这个神奇的东西，大致是一个可以 Serialize/Deserialize 一棵树的东西。利用这个东西呢，可以推出在 $n$ 个点的图中，使所有 $k$ 个联通块加 $k-1$ 条边联通的方案数恰好是$n^{k-2}\cdot\prod\limits_{i=1}^k siz_i$
然后呢，就比较好做了。
Case 1. 原本就有个环
数一下联通块，直接上Prufer联通求方案数即可。
Case 2. 原本没有环
首先加上没有环的方案数量（同 Case 1）。
之后我们就要给它造环了。
我们可以造一个跨越一个联通块、两个联通块或多个联通块的环。
Case 2.1. 跨一个联通块
在联通块中任意连上一个之前没有的边。
Case 2.2. 跨两个联通块
在两个联通块之间连两条边（注意不要重边啦）
Case 2.3. 跨多个联通块
我们可以圆排列一下，然后在两个挨着的联通块之间连一条边。
最后把环理解成是一个联通块，然后按照 Case 1 处理即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1234567891,inv2=617283946;
inline ll qpow(ll x,int p){
ll ans=1;
while(p){
if(p&1)ans=ans*x%mod;
x=x*x%mod;
p>>=1;
}
return ans;
}
inline int popcount(int x){
int res=0;
while(x){x-=x&-x;res++;}
return res;
}
class TheCitiesAndRoadsDivOne{
int n;
int conn[22][22],fa[22],siz[22],blkcnt=0,blksiz[22];
ll fac[22];
inline int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
public:
int find(vector<string> mp){
n=mp.size();
fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)conn[i+1][j+1]=(mp[i][j]=='Y');
for(int i=1;i<=n;++i)fa[i]=i,siz[i]=1;
bool ring=0;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(!conn[i][j])continue;
int fai=findfa(i),faj=findfa(j);
if(fai==faj){
ring=1;
}else siz[fai]+=siz[faj];
fa[faj]=fai;
}
}
ll res1;
ll pisiz=1;
for(int i=1;i<=n;++i)if(findfa(i)==i)blksiz[++blkcnt]=siz[i],(pisiz*=siz[i])%=mod;
if(blkcnt==1)res1=1;
else{
res1=qpow(n,blkcnt-2)*pisiz%mod;
}
if(ring)return res1;
ll res2=0;
for(int i=1;i<(1<<blkcnt);++i){
ll newsiz=0,tmp=1;
int pop=popcount(i);
if(pop==1){
int blk=log2(i)+1;
tmp=blksiz[blk]*(blksiz[blk]-1)/2-(blksiz[blk]-1);
newsiz=blksiz[blk];
}else if(pop==2){
int blk1=log2(i&-i)+1,blk2=log2((i^(i&-i))&(-(i^(i&-i))))+1;
tmp=blksiz[blk1]*blksiz[blk2];
tmp=tmp*(tmp-1)/2;
newsiz=blksiz[blk1]+blksiz[blk2];
}else{
tmp=fac[pop-1];
for(int j=0;j<blkcnt;++j){
if((i>>j)&1){
tmp=tmp*blksiz[j+1]%mod*blksiz[j+1]%mod;
newsiz+=blksiz[j+1];
}
}
tmp=tmp*inv2%mod;
}
pisiz=newsiz;
for(int j=0;j<blkcnt;++j)if(!((i>>j)&1))pisiz=pisiz*blksiz[j+1]%mod;
int newblkcnt=blkcnt-popcount(i)+1;
if(newblkcnt==1){
(res2+=tmp)%=mod;
continue;
}
tmp=tmp*qpow(n,newblkcnt-2)%mod*pisiz%mod;
(res2+=tmp)%=mod;
}
return (res1+res2)%mod;
}
};