题目传送门
题目大意：有$n$个小岛，每个小岛上有$a_{i}$个城市，同一个小岛上的城市互相连接形成一个完全图，第$i$个小岛的第$a_{i}$个城市和第$i+1$个小岛的第$1$个城市连接，特别地，第$n$个小岛的第$a_{n}$个城市和第$1$个小岛的第$1$个城市连接。现在要断掉图中的一些边，保证任意两个城市只有一条路径或者不连通，求合法的断边方案总数，$n,a_{i}<=1e5$
完全不会（喷血
我们对每个小岛单独讨论
如果任意两个城市只有一条路径或者不连通，那么这张图只能是一个森林
定义$f[i]$表示$i$个点的完全图的答案
我们对第$i$个点所在的树进行讨论， 设$i$点所在的树除了$i$点还有$j$个节点，可以得到方程
$f[i]=sumlimits_{j=0}^{i-1} C_{i-1}^{j}f[i-j-1](j+1)^{j-1}$
完全图有标号生成树个数是$n^{n-2}$
把上述式子展开，发现是一个卷积形式，可以用分治$NTT$求解
显然小岛间的边至少断一条就ok了
如果一条都不断边呢？
就要保证至少一个小岛内的$1$号点和$a_{i}$号点不连通
我们去掉每个小岛的$1$号点和$a_{i}$号点都连通的方案数就行了
这种情况的$DP$方程和上面的差不多， 设$i$点所在的树除了$i$点和$1$号点还有$j$个节点
$g[i]=sumlimits_{j=0}^{i-2} C_{i-1}^{j-1}f[i-j-2](j+2)^{j}$
不用分治直接$NTT$就行了
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define N1 (1<<18)+10 6 #define il inline 7 #define dd double 8 #define ld long double 9 #define ll long long 10 using namespace std; 11 12 const int inf=0x3f3f3f3f; 13 const ll p=998244353; 14 int gint() 15 { 16 int ret=0,fh=1;char c=getchar(); 17 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 18 while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();} 19 return ret*fh; 20 } 21 ll qpow(ll x,ll y) 22 { 23 ll ans=1; 24 for(;y>0;x=x*x%p,y>>=1) if(y&1) ans=ans*x%p; 25 return ans; 26 } 27 28 int T,n,m; 29 namespace NTT{ 30 ll a[N1],b[N1],c[N1],Wn[N1],_Wn[N1]; 31 int r[19][N1]; 32 void Pre(int len,int L) 33 { 34 int i,j; 35 for(j=1;j<=L;j++) for(i=0;i<(1<<j);i++) 36 r[j][i]=(r[j][i>>1]>>1)|((i&1)<<(j-1)); 37 for(i=1;i<=len;i<<=1) Wn[i]=qpow(3,(p-1)/i), _Wn[i]=qpow(Wn[i],p-2); 38 } 39 void NTT(ll *s,int len,int type,int L) 40 { 41 int i,j,k; ll wn,w,t; 42 for(i=0;i<len;i++) if(i<r[L][i]) swap(s[i],s[r[L][i]]); 43 for(k=2;k<=len;k<<=1) 44 { 45 wn=(type>0)?Wn[k]:_Wn[k]; 46 for(i=0;i<len;i+=k) 47 { 48 for(j=0,w=1;j<(k>>1);j++,w=w*wn%p) 49 { 50 t=w*s[i+j+(k>>1)]%p; 51 s[i+j+(k>>1)]=(s[i+j]+p-t)%p; 52 s[i+j]=(s[i+j]+t)%p; 53 } 54 } 55 } 56 } 57 void Main(int len,int L) 58 { 59 int i,invl=qpow(len,p-2); 60 NTT(a,len,1,L); NTT(b,len,1,L); 61 for(i=0;i<len;i++) c[i]=a[i]*b[i]%p; 62 NTT(c,len,-1,L); 63 for(i=0;i<len;i++) c[i]=c[i]*invl%p; 64 } 65 void clr(int sz) 66 { 67 memset(a,0,sz<<3); 68 memset(b,0,sz<<3); 69 } 70 }; 71 72 using NTT::a; using NTT::b; using NTT::c; 73 ll F1[N1],F2[N1],f[N1],g[N1],mul[N1],_mul[N1]; 74 void CDQ(int l,int r) 75 { 76 if(r-l==1&&l) 77 { 78 F1[l]=(f[l]*mul[l-1]%p+qpow(l,l-2))%p; 79 f[l]=F1[l]*_mul[l]%p; 80 } 81 if(r-l<=1) return; 82 int mid=(l+r)>>1,i,len,L; 83 CDQ(l,mid); 84 for(len=1,L=0;len<(mid-l)+(r-l)-1;len<<=1,L++); 85 for(i=l;i<mid;i++) NTT::a[i-l]=f[i]; 86 for(i=0;i<(r-l);i++) NTT::b[i]=g[i]; 87 NTT::Main(len,L); 88 for(i=mid;i<r;i++) f[i]=(f[i]+NTT::c[i-l])%p; 89 NTT::clr(len); 90 CDQ(mid,r); 91 } 92 int v[5][N1],sz[5]; 93 94 int main() 95 { 96 scanf("%d",&T); 97 int i,j,x,y,len,L,t; 98 for(t=0;t<T;t++) 99 { 100 sz[t]=gint(); 101 for(i=1;i<=sz[t];i++) v[t][i]=gint(), n=max(n,v[t][i]); 102 } 103 for(len=1,L=0;len<n+n-1;len<<=1,L++); 104 NTT::Pre(len,L); 105 mul[0]=mul[1]=_mul[0]=_mul[1]=1; 106 for(i=2;i<=n;i++) mul[i]=mul[i-1]*i%p, _mul[i]=qpow(mul[i],p-2); 107 for(i=2,g[1]=1;i<=n;i++) g[i]=qpow(i,i-2)*_mul[i-1]%p; 108 CDQ(0,n+1); 109 for(i=0;i<=n;i++) NTT::a[i]=F1[i]*_mul[i]%p; NTT::a[0]=1; // f[j] / (j-1)! 110 for(i=2;i<=n;i++) NTT::b[i]=qpow(i,i-2)*_mul[i-2]%p; // j^(j-2) / (j-2)! NTT::b[1]=1; 111 NTT::Main(len,L); F2[1]=1; 112 for(i=2;i<=n;i++) F2[i]=mul[i-2]*NTT::c[i]%p; 113 for(t=0;t<T;t++) 114 { 115 ll ans=qpow(2,sz[t]),ret=1; 116 for(i=1;i<=sz[t];i++) ans=ans*F1[v[t][i]]%p; 117 for(i=1;i<=sz[t];i++) ret=ret*F2[v[t][i]]%p; 118 ans=(ans+p-ret)%p; 119 printf("%lld ",ans); 120 } 121 return 0; 122 123 }