网站设计师培训图片,网站开发做什么科目,衡水教育行业网站建设,外贸网站建设商家传送门
题意#xff1a;给定nnn和集合SSS,求出nnn个点的「所有极大点双连通分量的大小都在SSS 内」的不同简单无向连通图的个数 模 998244353998244353998244353。 n,∑i∈Si≤105n,\sum_{i\in S}i \leq10^5n,∑i∈Si≤105
道理我都懂#xff0c;可为啥我百度搜地灵殿ex终…传送门
题意给定nnn和集合SSS,求出nnn个点的「所有极大点双连通分量的大小都在SSS 内」的不同简单无向连通图的个数 模 998244353998244353998244353。
n,∑i∈Si≤105n,\sum_{i\in S}i \leq10^5n,∑i∈Si≤105
道理我都懂可为啥我百度搜地灵殿ex终符一半都是cookie☆同人OI题
思路挺清奇的
首先注意题目中的点双定义是不存在割点也就是说只有两个点的连通图也是点双
同时一个点可能属于多个点双
显然要设出答案的EGF
因为无向图关系很复杂所以我们要强行整点东西上去
设[xn]F(x)[x^n]F(x)[xn]F(x)表示 nnn个点 带标号 有根 满足题目条件 的方案数 的EGF
有根是指每张图钦定一个根如果两张图边完全相同但根不同也视为不同的图
其实就是乘一个nnn
考虑怎么表示出F(x)F(x)F(x)
对于一张有根图我们把根删掉这样会出现多个连通块
对于每个连通块会发现都会有若干点和根处于同一个点双内
但是不会有不同连通块的点处于同一点双因为根结点删去后它们分开了与定义矛盾
考虑一个连通块的情况
先考虑根结点所在的点双大小发现同一组点组成的点双也有多种连边方案
设ana_nan表示n1n1n1个点构成的带标号点双个数
再设出满足题目要求的点双的EGF
A(x)∑i1∈Saii!xiA(x)\sum_{i1\in S}\frac{a_i}{i!}x^iA(x)i1∈S∑i!aixi
因为没有跨连通块所以这个连通块的点双一定在SSS内
然后将点双中的所有边删掉这样点双中的点两两间都不会连通 因为如果连通由于内部边都断完了只能走外面的点而经过的点都会在这个点双内
也就是说这个大连通块被分成了若干小连通块且连通块个数等于点双的大小不含根,小连通块的根是原来的点双中的点
这样可以写出一个大连通块的EGF
∑i1∞aii!Fi(x)\sum_{i1}^{\infin}\frac{a_i}{i!}F^i(x)i1∑∞i!aiFi(x)
也就是A(F(x))A(F(x))A(F(x))
注意这个过程并没有选出点双中有哪些点只是把连通块中的点分组并将每组的根按点双的方式连接起来
然后F(x)F(x)F(x)可以表示成任意个数连通块组合再加上根
也就是
F(x)xeA(F(x))F(x)xe^{A(F(x))}F(x)xeA(F(x))
假设我们已经求出了A(x)A(x)A(x)我们尝试算出F(x)F(x)F(x)
F(x)eA(F(x))x{F(x)\over e^{A(F(x))}}xeA(F(x))F(x)x
设
f(F(x))F(x)eA(F(x))xf(F(x)){F(x)\over e^{A(F(x))}}xf(F(x))eA(F(x))F(x)x
即fff和FFF互为复合逆
而
f(x)xeA(x)f(x)\frac{x}{e^{A(x)}}f(x)eA(x)x
显然[x0]A(x)0[x^0]A(x)0[x0]A(x)0,所以可以算出f(x)f(x)f(x)进而用拉格朗日反演算出[xn]F(x)[x^n]F(x)[xn]F(x) 现在的问题是如何求A(x)A(x)A(x)
直接求不好求考虑构造一个相似的问题用其他方法算一次再把A(x)A(x)A(x)反推回来
那考虑减少限制 发现减掉在SSS中的限制也就是任意连通图我们也可以用这个思路计算
并且这是一道原题
城市规划
直接取对数就可以轻松算出答案岂不美哉
好我们仿fu照zhi这道题算出任意无向连通图的EGF G(x)G(x)G(x),并乘一个nnn上个根
现在G(x)G(x)G(x) 已知了
设
B(x)∑i1∞aii!xiB(x)\sum_{i1}^{\infin} \frac{a_i}{i!}x^iB(x)i1∑∞i!aixi
相同的思路得到
G(x)xeB(G(x))G(x)xe^{B(G(x))}G(x)xeB(G(x))
G(x)eB(G(x))x\frac{G(x)}{e^{B(G(x))}}xeB(G(x))G(x)x
g(G(x))G(x)eB(G(x))xg(G(x))\frac{G(x)}{e^{B(G(x))}}xg(G(x))eB(G(x))G(x)x
g(x)xeB(x)g(x)\frac{x}{e^{B(x)}}g(x)eB(x)x
变一下可以得到
B(x)ln(xg(x))B(x)\ln(\frac{x}{g(x)})B(x)ln(g(x)x)
用拉格朗日反演算出g(x)g(x)g(x)……
拉个鬼啊一次拉格朗日反演就是O(nlogn)O(nlogn)O(nlogn)的你要算出g(x)g(x)g(x)就要跑nnn次再怎么也有O(n2)O(n^2)O(n2)了吧
但我们注意到A(x)A(x)A(x)有值的地方很少而且下标和不超过1e51e51e5所以如果我们直接拉出A(x)A(x)A(x)就没有复杂度问题啦
好整理一下已知条件
g(G(x))G(x)eB(G(x))xg(G(x))\frac{G(x)}{e^{B(G(x))}}xg(G(x))eB(G(x))G(x)x
B(x)ln(xg(x))B(x)\ln(\frac{x}{g(x)})B(x)ln(g(x)x)
闲着没事把上面代到下面
注这里为了统一代码改一下
B(G(g(x)))ln(xg(x))B(G(g(x)))\ln(\frac{x}{g(x)})B(G(g(x)))ln(g(x)x)
好多括号啊拆掉里面那个
B(G(x))ln(G(x)x)B(G(x))\ln(\frac{G(x)}{x})B(G(x))ln(xG(x)) 停我说一句
有个叫扩展拉格朗日反演的东西,长这样:
[xn]H(G(x))1n[x−1]H′(x)Fn(x)[x^n]H(G(x))\frac{1}{n}[x^{-1}]\frac{H(x)}{F^n(x)}[xn]H(G(x))n1[x−1]Fn(x)H′(x)
证明的话在G(F(x))xG(F(x))xG(F(x))x两边同时复合一个H(x)H(x)H(x),并令H(G(x))T(x)H(G(x))T(x)H(G(x))T(x)后面就一模一样了 好继续
我们强行构造上面的结论令
H(g(x))B(x)H(g(x))B(x)H(g(x))B(x)
这样
[xn]B(x)[xn]H(g(x))1n[x−1]H′(x)Gn(x)[x^n]B(x)[x^n]H(g(x))\frac{1}{n}[x^{-1}]\frac{H(x)}{G^n(x)}[xn]B(x)[xn]H(g(x))n1[x−1]Gn(x)H′(x)
就可以把B(x)B(x)B(x)算出来
现在只需要求出H(x)H(x)H(x)
由于
H(g(x))B(x)H(g(x))B(x)H(g(x))B(x)
得到
H(x)H(g(G(x)))B(G(x))ln(G(x)x)H(x)H(g(G(x)))B(G(x))\ln(\frac{G(x)}{x})H(x)H(g(G(x)))B(G(x))ln(xG(x))
并不需要手动算除出来O(n)O(n)O(n)挪一下就可以了
把读入的位置拉出来直接丢到A(x)A(x)A(x)的对应位置然后推出F(x)F(x)F(x)即可
#include iostream
#include cstdio
#include cstring
#include cctype
#include ctime
#define MAXN 400005
using namespace std;
const int MOD998244353;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
typedef long long ll;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD;p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
int fac[MAXN],finv[MAXN];
int rt[2][24];
int l,r[MAXN];
inline void init(){for (int i0;i(1l);i) r[i](r[i1]1)|((i1)(l-1));}
inline void NTT(int* a,int type)
{int lim1l;for (int i0;ilim;i) if (ir[i]) swap(a[i],a[r[i]]);for (int L0;Ll;L){int mid1L,lenmid1,Wnrt[type][L1];for (int s0;slim;slen)for (int k0,w1;kmid;k,w(ll)w*Wn%MOD){int xa[sk],y(ll)w*a[smidk]%MOD;a[sk]add(x,y);a[smidk]dec(x,y);}}if (type){int tinv(lim);for (int i0;ilim;i) a[i](ll)a[i]*t%MOD;}
}
void getinv(int* A,int* B,int n)
{static int f[MAXN],t[MAXN];if (n1) return (void)(*Binv(*A));getinv(A,t,(n1)1);for (l0;(1l)(n1);l);init();for (int i0;in;i) f[i]A[i];for (int in;i(1l);i) f[i]t[i]0;NTT(f,0);NTT(t,0);for (int i0;i(1l);i) B[i](ll)t[i]*dec(2,(ll)f[i]*t[i]%MOD)%MOD;NTT(B,1);for (int in;i(1l);i) B[i]0;
}
inline void deriv(int* A,int* B,int n){for (int i0;in-1;i) B[i](ll)A[i1]*(i1)%MOD;B[n-1]0;}
inline void integ(int* A,int* B,int n){for (int i1;in;i) B[i](ll)A[i-1]*fac[i-1]%MOD*finv[i]%MOD;B[0]0;}
void getln(int* A,int* B,int n)
{static int f[MAXN],g[MAXN];deriv(A,f,n);getinv(A,g,n);for (int in;i(1l);i) f[i]g[i]0;NTT(f,0);NTT(g,0);for (int i0;i(1l);i) f[i](ll)f[i]*g[i]%MOD;NTT(f,1);integ(f,B,n);for (int in;i(1l);i) B[i]0;
}
void getexp(int* A,int* B,int n)
{static int f[MAXN],g[MAXN];if (n1) return (void)(*B1);getexp(A,g,(n1)1);getln(g,f,n);for (int i0;in;i) f[i]dec(A[i],f[i]);f[0];for (int in;i(1l);i) f[i]g[i]0;NTT(f,0);NTT(g,0);for (int i0;i(1l);i) B[i](ll)f[i]*g[i]%MOD;NTT(B,1);for (int in;i(1l);i) B[i]0;
}
void getpow(int* A,int* B,int n,int k)
{static int t[MAXN];getln(A,t,n);for (int i0;in;i) t[i](ll)t[i]*k%MOD;getexp(t,B,n);
}
int G[MAXN],H[MAXN],dH[MAXN],A[MAXN],t[MAXN],f[MAXN];
int LangInv(int* F,int n,bool exfalse)
{static int f[MAXN],g[MAXN];for (int i0;in;i) f[i]F[i1];f[n]0;getinv(f,g,n);getpow(g,f,n,n);int ans0;if (ex) for (int i0;in;i) ansadd(ans,(ll)dH[i]*f[n-i-1]%MOD);else ansf[n-1];return (ll)ans*fac[n-1]%MOD*finv[n]%MOD;
}
time_t START;
int main()
{fac[0]1;for (int i1;iMAXN;i) fac[i](ll)fac[i-1]*i%MOD;finv[MAXN-1]inv(fac[MAXN-1]);for (int iMAXN-2;i0;i--) finv[i](ll)finv[i1]*(i1)%MOD;rt[0][23]qpow(3,119);rt[1][23]inv(rt[0][23]);for (int i22;i0;i--){rt[0][i](ll)rt[0][i1]*rt[0][i1]%MOD;rt[1][i](ll)rt[1][i1]*rt[1][i1]%MOD;}int nread();for (int i0;in;i) t[i](ll)qpow(2,((ll)i*(i-1)/2)%(MOD-1))*finv[i]%MOD;getln(t,G,n1);for (int i0;in;i) G[i](ll)G[i]*i%MOD;for (int i0;in;i) t[i]G[i1];t[n]0;getln(t,H,n1);deriv(H,dH,n1);for (int sread();s;s--){int pread()-1;A[p]LangInv(G,p,true);}getexp(A,t,n1);getinv(t,A,n1);for (int i1;in;i) f[i]A[i-1];f[0]0;printf(%d\n,(ll)LangInv(f,n)*fac[n-1]%MOD);return 0;
}P.S. 如果你用LOJ的CNOI T成了狗试试C……
