[bzoj5093][Lydsy1711月赛]图的价值

要是再不写题解我又双叒叕忘了斯特林转下降幂咋写了…… 题目简单易懂，所有求n个点带标号的无向图中每个点度数的k次方之和 换句话讲，两个图不同当且仅当邻接矩阵不同 那么我们不妨考虑每个点对答案的贡献,我们发现每个点是平权的，因此只需要计算出每个点对答案的贡献然后乘上一个$n$就行了 接下来我们计算每个点的贡献的时候只需要枚举他的度数然后统计贡献就行了,由于无论这个点的度数如何剩下的点总是可以随便连边，因此这种图一共会有$2^{n-1 \choose 2 }$种方案 所以说了这么多只是想说明一件事就是答案的式子就是 $$n2^{n-1 \choose 2}\sum_{i=0}^{n-1}{n-1 \choose i}i^k$$ 前面的式子显然是个常量可以直接计算 让我们来把注意力放在后边的式子上 $$\sum_{i=0}^{n-1}{n-1 \choose i}i^k$$ 然后这里会有一个非常黑科技的东西就是我们可以使用斯特林数来强行把$i^k$拆开 具体来讲我们有这么一个式子 ~~(顺便说一句斯特林数用latex真的难打，接下来你看到的东西读作斯特林数其实是强行拿矩阵拼出来的)~~ $$n^k=\sum_{i=0}^{k}\left\{ \begin{matrix} k \\ i\end{matrix} \right\}{n \choose i}i!$$ 通过组合意义解释一下上面的式子就是我们发现左边相当于把k个物品标n中不同颜色的方案数，那么我们枚举到底有几种颜色，这个就是和式当中的i的含义,然后通过斯特林数钦定一下哪些物品的颜色是相同的(k个物品划分成i个集合方案数),然后从n个颜色当中钦定i个颜色是组合数，最后由于集合划分是无序的，因此乘上一个$i!$保证有序性 ~~用上面的式子算出来0的0次幂是0~~ 那么我们把这个东西代入到刚才的式子中就是成了这个式子 $$\sum_{i=0}^{n-1}{n-1 \choose i}\sum_{j=0}^{k}\left\{ \begin{matrix} k \\ j \end{matrix} \right\}{i \choose j}j!$$ 通过一些交换求和号的常识我们可以把式子变成这样 $$\sum_{j=0}^{k}\left\{ \begin{matrix} k \\ j\end{matrix} \right\}j!\sum_{i=0}^{n-1}{n-1 \choose i}{i \choose j}$$ 其实式子推到这步一点长进没有……该不能做的还是不能做 不过让我们看看似乎还是有一点抢救的可能的，让我们将精力集中在和式的后半部分的组合意义上 $$\sum_{i=0}^{n-1}{n-1 \choose i}{i \choose j}$$ 这个东西的实际意义是从n个数字当中选择i个数字再从这i个数字当中选择j个数字 那么我们不妨考虑每一个size为j的子集被选了几次，显然这样的子集一共有${n-1 \choose j}$种，我们发现当钦定了j个位置之后剩下的位置其实是随便选的，因此每一个子集都被算了$2^{n-1-j}$次 因此我们的式子就化成了 $$\sum_{j=0}^{min(k,n-1)}\left\{ \begin{matrix} k \\ j\end{matrix} \right\}j!{n-1 \choose j}2^{n-1-j}$$ 好了看起来我们似乎可以$O(k)$的计算这个和式了？ 等等你组合数怎么算啊…… 我们发现一个比较有趣的事实是 $${n \choose j}j!=n^{ \underline j}$$ 显然下降幂还是比较亲民的…… 所以最后用来算答案的式子就是 $$\sum_{j=0}^{k}\left\{ \begin{matrix} k \\ j\end{matrix} \right\}2^{n-1-j}(n-1)^{\underline j}$$ 好了最后一个问题，我们怎么算第二类斯特林数？ 把第二类斯特林数的定义念一遍：将n个元素划分为m个集合的方案数 也是将$n$个有区别的球放到$m$个无区别盒子中的方案数,当然限制是允许任何盒子是空的 因此我们可以大力容斥一发,枚举有几个盒子是空的 $$\left\{ \begin{matrix} n \\ m\end{matrix} \right\}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{i}{m \choose i}(m-i)^{n}$$ 为什么上面的容斥是对的呢?首先$(-1)^{i}$是二项式反演配的系数这里就不多解释了，除m的阶乘是因为我们后边的计数方式是将盒子看成互不相同的，因此需要除上一个阶乘 那么组合数的含义就好解释了,从m个盒子当中钦定i个空盒子，而$(m-i)^n$的意义也很好解释了,还剩下$(m-i)$个有球的盒子,随便选就行了 那么我们将组合数拆一拆 $$\left\{ \begin{matrix} n \\ m\end{matrix} \right\}=\sum_{i=0}^{m}\frac{(-1)^i}{i!}×\frac{(m-i)^{n}}{(m-i)!}$$ 那么如果我们令 $$f(k)=\left\{ \begin{matrix} n \\ k\end{matrix} \right\}$$ $$g(k)=\frac{(-1)^k}{k!}$$ $$h(k)=\frac{k^n}{k!}$$ 我们会得到 $$f(k)=\sum_{i+j=k}g(i)h(j)$$ 这是个标准卷积形式，直接ntt就行了 然后就做完了 上代码~ ```C /************************************************************** Problem: 5093 User: shadowice1984 Language: C++ Result: Accepted Time:16904 ms Memory:15160 kb ****************************************************************/ #include<cstdio> #include<algorithm> using namespace std;typedef long long ll;const ll mod=998244353;const int N=524288+10; int rv[N];ll rt[2][22]; inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;} inline void ntt(ll* a,int len,int o) { for(int i=0;i<len;i++)if(i<rv[i])swap(a[i],a[rv[i]]); for(int k=1,j=1;k<len;k<<=1,j++) for(int s=0;s<len;s+=(k<<1)) for(int i=s,w=1;i<s+k;i++,w=w*rt[o][j]%mod) {ll a1=a[i+k]*w%mod;a[i+k]=(a[i]+mod-a1)%mod;(a[i]+=a1)%=mod;} if(o){ll inv=po(len,mod-2);for(int i=0;i<len;i++)(a[i]*=inv)%=mod;} }ll f1[N];ll st[N];ll ifac[N];ll n;int k;ll ans; int main() { for(int i=1,t=(mod-1)/2;i<=20;i++,t>>=1)rt[0][i]=po(3,t); for(int i=1,t=(mod-1)/2;i<=20;i++,t>>=1)rt[1][i]=po(332748118,t); scanf("%lld%d",&n,&k);ifac[0]=ifac[1]=1; for(int i=2;i<=k;i++)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod; for(int i=1;i<=k;i++)(ifac[i]*=ifac[i-1])%=mod; for(int i=0;i<=k;i++)f1[i]=(i&1)?(mod-ifac[i])%mod:ifac[i]; for(int i=0;i<=k;i++)st[i]=ifac[i]*po(i,k)%mod; int len=1;int d=0;for(;len<=k;len<<=1,d++);len<<=1;d++; for(int i=1;i<len;i++)rv[i]=(rv[i>>1]>>1)|((i&1)<<(d-1)); ntt(f1,len,0);ntt(st,len,0);for(int i=0;i<len;i++)(st[i]*=f1[i])%=mod;ntt(st,len,1); for(ll t=0,dw=1;t<=min((ll)k,n-1);t++,(dw*=(n-t))%=mod) (ans+=st[t]*dw%mod*po(2,n-1-t))%=mod; printf("%lld",ans*n%mod*po(2,((n-2)*(n-1)/2)%(mod-1))%mod);return 0; } ```