bzoj 5093 图的价值

题目大意：

求所有n个点的带标号的简单无向图的价值之和

一个带标号的图的价值定义为每个点度数的k次方的和

思路：

枚举每个点的度数，以及选哪些点与其相连，其他的边无所谓，则该点的贡献为$2^{m-n+1}sumlimits_{i=0}^n inom{n-1}{i} * i^k $

由于所有点是等价的因此总答案为$n * 2^{m-n+1}sumlimits_{i=0}^n inom{n-1}{i} * i^k $

把$i^k$拆开得到$n * 2^{m-n+1}sumlimits_{i=0}^n inom{n-1}{i} sumlimits_{j=0}^k inom{i}{j} *S2(k,j)*j!$

交换求和顺序得到：$n * 2^{m-n+1} sumlimits_{j=0}^k *S2(k,j)*j! sumlimits_{i=0}^n inom{n-1}{i} inom{i}{j} $

把后面的组合数拆开得到：$n * 2^{m-n+1} sumlimits_{j=0}^k *S2(k,j)*j! sumlimits_{i=0}^n frac{(n-1)!}{(i!)*(n-1-i)!}frac{i!}{(j!)*(i-j)!} $

把$i!$约掉再上下同乘$(n-j)!$ ，得到：$frac{(n-1)!}{(j!)*(n-1-j)!} frac{(n-1-j)!}{(i-j)!*(n-i-1)!}=inom{n-1}{j} inom{n-1-j}{i-j}$

提出$inom{n-1}{j}$ 得到：$n * 2^{m-n+1} sumlimits_{j=0}^k *S2(k,j)*j! * inom{n-1}{j}sumlimits_{i=0}^n inom{n-1-j}{i-j}$

发现后面是一整行的杨辉三角变成$2^{n-1-j}$得：$n * 2^{m-n+1} sumlimits_{j=0}^k *S2(k,j)*j! * inom{n-1}{j} *2^{n-1-j}$

那么需要求出斯特林数即可。把斯特林数拆开得到$f(i)=frac{(-1)^i}{i!},g(i)=frac{i^k}{i!}$ 卷积之后得到斯特林数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define db double
13 #define inf 2139062143
14 #define MAXN 400100
15 #define MOD 998244353
16 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
17 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
18 #define ren for(register int i=fst[x];i;i=nxt[i])
19 #define pb(i,x) vec[i].push_back(x)
20 #define pls(a,b) ((a+b)%MOD+MOD)%MOD
21 #define mns(a,b) ((a%MOD-(b)%MOD)%MOD+MOD)%MOD
22 #define mul(a,b) (1LL*(a)*(b))%MOD
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
28     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
29     return x*f;
30 }
31 int n,k,a[MAXN<<1],b[MAXN<<1],fac[MAXN],ifac[MAXN];
32 int rev[MAXN<<1],lim,lg,pw[30],ipw[30],ans;
33 int q_pow(int bas,int t,int res=1)
34 {
35     for(;t;t>>=1,bas=mul(bas,bas)) if(t&1) res=mul(res,bas);return res;
36 }
37 #define inv(x) q_pow(x,MOD-2)
38 void ntt(int *a,int n,int f)
39 {
40     rep(i,0,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
41     for(int i=1,t=1;i<n;i<<=1,++t)
42     {
43         int wn= f>0?pw[t]:ipw[t];for(int j=0;j<n;j+=i<<1)
44         {
45             int w=1,x,y;for(int k=0;k<i;++k,w=mul(w,wn))
46                 x=a[j+k],y=mul(a[j+k+i],w),a[j+k]=pls(x,y),a[j+k+i]=mns(x,y);
47         }
48     }
49     if(f>0) return ;int nv=inv(n);rep(i,0,n-1) a[i]=mul(a[i],nv);
50 }
51 int main()
52 {
53     n=read(),k=read();fac[0]=ifac[0]=1;rep(i,1,k) fac[i]=mul(fac[i-1],i),ifac[i]=inv(fac[i]);
54     int tmp=-1;rep(i,0,k) tmp=(MOD-tmp)%MOD,a[i]=mul(tmp,ifac[i]);
55     rep(i,1,k) b[i]=mul(ifac[i],q_pow(i,k));
56     for(lim=1,lg=1;lim<=(k+1<<1);lim<<=1,lg++)
57         pw[lg]=q_pow(3,(MOD-1)/(1<<lg)),ipw[lg]=inv(pw[lg]);
58     rep(i,1,lim-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-2);
59     ntt(a,lim,1);ntt(b,lim,1);rep(i,0,lim-1) a[i]=mul(a[i],b[i]);ntt(a,lim,-1);
60     tmp=1;rep(i,0,k) ans=pls(ans,mul(mul(tmp,a[i]),q_pow(2,(n-2-i+MOD)%(MOD-1)))),tmp=mul(tmp,n-1-i);
61     printf("%d
",mul(mul(ans,n),q_pow(2,((1LL*n*(n-1)>>1)-n+1)%(MOD-1))));
62 }

View Code