「NOI十联测」黑暗

\(n\) 个点的无向图，每条边都可能存在，一个图的权值是连通块个数的 \(m\) 次方，求所有可能的图的权值和。(n≤30000,m≤15)

令\(ans[n][m]\)为n个点,图的权值是连通块个数的 m 次方,最终的答案.

\(g[i]\)为\(i\)个点无向联通图数目.

一个图，若连通块数T增加1，那么贡献为\(\displaystyle (T+1)^m=\sum_{i=0}^m C_m^i T^i\).

这里选取\(i\)个点组成一个连通块（包含一个指定的点），联通块数目增加1.

\[ans[n][m]=\sum_{i=1}^{n} g_i C_{n-1}^{i-1} (\sum_{j=0}^m C_m^j ans[n-i][j])
\]

\[ans[n][m]=m!(n-1)! \sum_{i=1}^{n} {g_i \over (i-1)！}{{\sum_{j=0}^m {ans[n-i][j]\over j! (m-j)!}} \over (n-i)!}
\]

令 \(\displaystyle T[i][j]=\sum_{k=0}^j {ans[i][k]\over k! (j-k)!}\)

\[ans[n][m]=m!(n-1)! \sum_{i=1}^{n} {g_i \over (i-1)！}{ T[n-i][m] \over (n-i)!}
\]

枚举m.

m=0的时候ans即为图的个数.

之后分治FFT...

复杂度\(O(nmlog(n^2)+nm^2)\).

代码里把\(i=n\)单独提出，其实可以不提出。

#include<bits/stdc++.h>

#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)

#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)

#define mem(a,b) memset(a,b,sizeof a )

#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl

using namespace std;

void in(int &r) {

	static char c;

	r=0;

	while(c=getchar(),!isdigit(c));

	do r=(r<<1)+(r<<3)+(c^48);

	while(c=getchar(),isdigit(c));

}

const int mn=30005;

const int mod=998244353;

int mul[mn],inv[mn];

int all[mn],un_able[mn],_able[mn];

int mlv(int x,int v){

    int ans=1;

    while(v){

	    if(v&1)ans=1LL*ans*x%mod;

	    x=1LL*x*x%mod,v>>=1;

	}

	return ans;

}

namespace NTT{

    const int g=3;

    const int gg=332748118;

    int n,lim,to[66000];

    void DFT(int* a,int iv){

	    rep(q,0,n-1)if(to[q]<q)swap(a[q],a[to[q]]);

	    for(int len=2;len<=n;len<<=1){

		    int mv=1,ml=mlv(iv?g:gg,(mod-1)/len),sp=len>>1;

		    for(int k=0;k<sp;++k){

			    for(int* p=a;p!=a+n;p+=len){

				    int mid=1LL*p[k+sp]*mv%mod;

				    p[k+sp]=(p[k]-mid)%mod;

				    p[k]=(p[k]+mid)%mod;

				}

				mv=1LL*mv*ml%mod;

			}

		}

	}

	void solve(int* a,int len1,int* b,int len2,int* c){

	    n=1,lim=0;

	    while(n<(len1+len2))n<<=1,++lim;

	    rep(q,len1,n-1)a[q]=0;

	    rep(q,len2,n-1)b[q]=0;

	    rep(q,0,n-1)to[q]=to[q>>1]>>1 | (q&1)<<(lim-1);

	    DFT(a,1),DFT(b,1);

	    rep(q,0,n-1)c[q]=1LL*a[q]*b[q]%mod;

	    DFT(c,0);

	    int inv_n=mlv(n,mod-2);

	    rep(q,0,n-1)c[q]=1LL*c[q]*inv_n%mod;

	    rep(q,0,n-1)c[q]=(c[q]+mod)%mod;

	}

}

int dp[mn],dp1[mn],A[66000],B[66000],C[66000];

void solve(int l,int r){

	if(l>r)return;

    if(l==r){

    	un_able[l]=1LL*un_able[l]*mul[l-1]%mod;

	    _able[l]=((long long)all[l]-un_able[l]+mod)%mod;

	    return;

	}

	int mid=l+r>>1;

	solve(l,mid);

	rep(q,l,mid)A[q-l]=1LL*_able[q]*inv[q-1]%mod;

	rep(q,1,r-l)B[q-1]=1LL*all[q]*inv[q]%mod;

	NTT::solve(A,mid-l+1,B,r-l,C);

	rep(q,mid+1,r)un_able[q]=(un_able[q]+C[q-l-1])%mod;

	solve(mid+1,r);

}

int ans[16][30005],mid[16][30005],nw;

int *md,*md1;

void cdq(int l,int r){

    if(l>r)return;

    if(l==r){

	    md[l]=1LL*mul[nw]*mul[l-1]%mod*md[l]%mod;

	    md[l]=(md[l]+_able[l])%mod;

	    rep(q,0,nw)md1[l]=(md1[l]+1LL*ans[q][l]*inv[q]%mod*inv[nw-q])%mod;

	    return;

	}

	int mid=l+r>>1;

	cdq(l,mid);

	rep(q,l,mid)A[q-l]=1LL*md1[q]*inv[q]%mod;

	rep(q,1,r-l)B[q-1]=1LL*_able[q]*inv[q-1]%mod;

	NTT::solve(A,mid-l+1,B,r-l,C);

	rep(q,mid+1,r)md[q]=(md[q]+C[q-l-1])%mod;

	cdq(mid+1,r);

}

struct qr{

    int a,b;

}st[1005];

int main(){

	freopen("dark.in","r",stdin);

	freopen("dark.out","w",stdout);

	int T,m,n=15;

	in(T);

	rep(q,1,T)in(st[q].a),in(st[q].b),n=max(n,st[q].a);

	mul[0]=1;

	rep(q,1,n)mul[q]=1LL*mul[q-1]*q%mod;

	inv[0]=inv[1]=1;

	rep(q,2,n)inv[q]=1LL*(mod-mod/q)*inv[mod%q]%mod;

	rep(q,1,n)inv[q]=1LL*inv[q]*inv[q-1]%mod;

	all[0]=1;

	rep(q,1,n)all[q]=mlv(2,q*(q-1)>>1);

	solve(1,n);

	md=ans[0],md1=mid[0];

	rep(q,1,n)md[q]=md1[q]=mlv(2,q*(q-1)>>1);

	rep(q,1,15){

		md=ans[q],md1=mid[q],nw=q;

	    cdq(1,n);

	}

	rep(q,1,T)printf("%d\n",ans[st[q].b][st[q].a]);

	return 0;

}

巴特西

「NOI十联测」黑暗

「NOI十联测」黑暗

最新文章

热门文章