深圳公司网站备案,免备案域名注册,孩子发烧反反复复不退烧怎么办,wordpress 点赞 用户题目链接 hdu5279 题解 给出若干个完全图#xff0c;然后完全图之间首尾相连并成环#xff0c;要求删边使得两点之间路径数不超过\(1\)#xff0c;求方案数 容易想到各个完全图是独立的#xff0c;每个完全图要删成一个森林#xff0c;其实就是询问\(n\)个点有标号森林的个… 题目链接 hdu5279 题解 给出若干个完全图然后完全图之间首尾相连并成环要求删边使得两点之间路径数不超过\(1\)求方案数 容易想到各个完全图是独立的每个完全图要删成一个森林其实就是询问\(n\)个点有标号森林的个数 设\(f[i]\)表示\(i\)个点有标号森林的个数 枚举第一个点所在树大小我们只需求出\(n\)个点有多少种树由\(purfer\)序容易知道是\(n^{n - 2}\) 那么有\[f[n] \sum\limits_{i 1}^{n} {n - 1 \choose i - 1}i^{i - 2}f[n - i]\] 化简一下\[f[n] (n - 1)!\sum\limits_{i 1}^{n}\frac{i^{i - 2}}{(i - 1)!} \times \frac{f[n - i]}{(n - i)!}\] 分治\(NTT\)即可 每个完全图的方案是\(f[a[i]]\)中间相连的\(n\)条边有\(2^n\)种方案由乘法原理乘起来即可 但是这样求出来的不是答案会多算一类情况 每个完全图的\(1\)和\(a_i\)相通且所有中介边存在 所以我们还需要计算\(g[i]\)表示\(i\)个点的森林\(1\)和\(i\)点在同一棵树内的方案数 显然\[g[n] \sum\limits_{i 2}^{n} {n - 2 \choose i - 2}i^{i - 2}f[n - i]\] 化简得\[g[n] (n - 2)!\sum\limits_{i 2}^{n} \frac{i^{i - 2}}{(i - 2)!} \times \frac{f[n - i]}{(n - i)!}\]\(NTT\)即可 最后答案减去\(g[a[i]]\)的乘积即可 复杂度\(O(nlog^2n)\) #includealgorithm
#includeiostream
#includecstring
#includecstdio
#includecmath
#includemap
#define Redge(u) for (int k h[u],to; k; k ed[k].nxt)
#define REP(i,n) for (int i 1; i (n); i)
#define mp(a,b) make_pairint,int(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pairint,int
#define LL long long int
using namespace std;
const int maxn 400005,maxm 100005,INF 1000000000;
inline int read(){int out 0,flag 1; char c getchar();while (c 48 || c 57){if (c -) flag -1; c getchar();}while (c 48 c 57){out (out 3) (out 1) c - 48; c getchar();}return out * flag;
}
const int G 3,P 998244353;
int R[maxn];
inline int qpow(int a,int b){int re 1;for (; b; b 1,a 1ll * a * a % P)if (b 1) re 1ll * re * a % P;return re;
}
void NTT(int* a,int n,int f){for (int i 0; i n; i) if (i R[i]) swap(a[i],a[R[i]]);for (int i 1; i n; i 1){int gn qpow(G,(P - 1) / (i 1));for (int j 0; j n; j (i 1)){int g 1,x,y;for (int k 0; k i; k,g 1ll * g * gn % P){x a[j k],y 1ll * g * a[j k i] % P;a[j k] (x y) % P,a[j k i] ((x - y) % P P) % P;}}}if (f 1) return;int nv qpow(n,P - 2); reverse(a 1,a n);for (int i 0; i n; i) a[i] 1ll * a[i] * nv % P;
}int f[maxn],g[maxn],fac[maxn],fv[maxn],p[maxn],N 100005;
int A[maxn],B[maxn];
void solve(int l,int r){if (l r){if (l 0) f[l] 1ll * f[l] * fac[l - 1] % P;return;}int mid l r 1;solve(l,mid);int n,m,L;m mid - l 1;for (int i 0; i m; i) A[i] 1ll * f[l i] * fv[l i] % P;m r - l;for (int i 0; i m; i) B[i] 1ll * p[i 1] * fv[i] % P;n 1; L 0; m mid r - (l 1) - 1;while (n m) n 1,L;for (int i 1; i n; i) R[i] (R[i 1] 1) | ((i 1) (L - 1));for (int i mid - l 1; i n; i) A[i] 0;for (int i r - l; i n; i) B[i] 0;NTT(A,n,1); NTT(B,n,1);for (int i 0; i n; i) A[i] 1ll * A[i] * B[i] % P;NTT(A,n,-1);for (int i mid - l,j mid 1; j r; i,j){f[j] (f[j] A[i]) % P;}solve(mid 1,r);
}
int b[maxn];
inline int C(int n,int m){if (m n) return 0;return 1ll * fac[n] * fv[m] % P * fv[n - m] % P;
}
void work(){fac[0] p[0] p[1] 1;for (int i 1; i N 2; i)fac[i] 1ll * fac[i - 1] * i % P;for (int i 2; i N 2; i)p[i] qpow(i,i - 2);fv[N 2] qpow(fac[N 2],P - 2); fv[0] 1;for (int i N 1; i; i--)fv[i] 1ll * fv[i 1] * (i 1) % P;f[0] 1;solve(0,N);A[0] A[1] 0;for (int i 2; i N; i) A[i] 1ll * p[i] * fv[i - 2] % P;for (int i 0; i N; i) B[i] 1ll * f[i] * fv[i] % P;int n 1,L 0;while (n (N 1)) n 1,L;for (int i 1; i n; i) R[i] (R[i 1] 1) | ((i 1) (L - 1));for (int i N 1; i n; i) A[i] 0;for (int i N 1; i n; i) B[i] 0;NTT(A,n,1); NTT(B,n,1);for (int i 0; i n; i) A[i] 1ll * A[i] * B[i] % P;NTT(A,n,-1);for (int i 2; i N; i) g[i] 1ll * A[i] * fac[i - 2] % P;g[1] 1;
}
int n,a[maxn],ans,ans2;
int main(){work();//REP(i,100) printf(%d ,f[i]); puts();//REP(i,100) printf(%d ,g[i]); puts();int T read();while (T--){n read();REP(i,n) a[i] read();ans qpow(2,n);REP(i,n) ans 1ll * ans * f[a[i]] % P;ans2 1;REP(i,n) ans2 1ll * ans2 * g[a[i]] % P;ans ((ans - ans2) % P P) % P;printf(%d\n,ans);}return 0;
}转载于:https://www.cnblogs.com/Mychael/p/9172482.html
