幻想乡三连B：连在一起的幻想乡

$G[k][x]$表示所有$x$个点的无向图中每一个图的边数的$k$次方之和。

$F[k][x]$就是在$G[k][x]$的基础上加了一个整体连通的性质。

有一个经典的套路就是对于$F$在对应的$G$中刨去枚举$1$号节点所在的连通块大小的答案。

最后一个难点就是对于形如$\sum(x+y)^2$可以转化为$\sum x^2 +2(\sum x)(\sum y)+\sum y^2$。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 2002

using namespace std;

int read(){

	int nm=0,fh=1; char cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

int G[3][M],F[3][M],C[M][M],num;

const int n=read(),mod=read();

int mul(int x,int y){return (LL)x*(LL)y%mod;}

int add(int x,int y){return (x+y)>=mod?x+y-mod:x+y;}

void upd(int &x,int y){x=add(x,y);}

int qpow(int x,int sq){

	if(sq<0) return 0;

	int res=1; x%=mod;

	while(sq){

		if(sq&1) res=mul(res,x);

		x=mul(x,x),sq>>=1;

	}

	return res;

}

int main(){

	C[0][0]=1;

	for(int i=1;i<=n;i++){

		num=(i*(i-1)>>1),C[i][0]=C[i][i]=1,G[0][i]=qpow(2,num),G[1][i]=mul(num,qpow(2,num-1));

		for(int j=0;j<i;j++)upd(G[2][i],mul(add(add(G[2][i-1],mul(j<<1,G[1][i-1])),mul(j*j,G[0][i-1])),C[i-1][j]));

		for(int j=1;j<i;j++){

			C[i][j]=add(C[i-1][j],C[i-1][j-1]),upd(F[0][i],mul(C[i-1][j-1],mul(F[0][j],G[0][i-j])));

			upd(F[1][i],mul(C[i-1][j-1],add(mul(F[1][j],G[0][i-j]),mul(F[0][j],G[1][i-j]))));

			upd(F[2][i],mul(C[i-1][j-1],add(add(mul(F[2][j],G[0][i-j]),mul(2,mul(F[1][j],G[1][i-j]))),mul(F[0][j],G[2][i-j]))));

		}

		for(int j=0;j<3;j++) F[j][i]=mod-F[j][i],upd(F[j][i],G[j][i]);

	}

	printf("%d\n",F[2][n]); return 0;

}

巴特西

幻想乡三连B：连在一起的幻想乡

最新文章

热门文章