题解 P5219 【无聊的水题 I】

· · 题解

某计数题题解

本文内容目录:

qwq,马上省选我才做了第一个多项式计数题

表示萌新afoier spinach在此对一直带我玩的各位dalao表示衷心感谢.

题目意思:
求n点,有标号,无根树,max_{x\in T}(deg_x)=m的图计数.

首先我们需要了解一个用于无根树计数的工具.prufer sequence.(不会打那个字符用u代替了...).
这是一个建立在 有标号无根树 和 数列 之间的一一映射. 具体说:一个n点有标号无根树,和一个长度为n-2,所有元素都在[1,n]内的数列有唯一对应关系.

当然这些都不重要

通过分析"有标号无根树 转 prufer sequence的算法",我们得到一个有用的性质:x在树中的度数等于在prufer序列中出现次数+1,deg(x)_{\text{ tree}}=count(x)_{\text{prufer sequence}}+1

回到本题,这是一个钦定最大度数(即出现次数)的序列计数问题...仍然不太好做,但是所有度数(出现次数)都不超过m的序列计数是好做的. 而且\leq m和\leq m+1相差的部分即为max(deg_x)=m+1的数量.

现在问题转化为这样元素都在[1,n]中,长度为n-2,每个元素出现次数不超过m的序列计数.

我们可以依靠 套路/直觉/乱搞 写出一个DP的计数玩法.

$$f_{x,len}=\sum_{i=0}^{min(len,m)}\binom{len}{i}f_{x-1,len-i}$$ 这个式子的组合意义是.考虑$x$出现次数为$i$,之前的元素构成了长度为$len-i$的序列,我们向其中插入一种从未出现过的元素$x$,共插入$i$次,能得到多少不同的序列. $len-i$个元素,将会有$len-i+1$个位置可以插入$x$(首尾和两两之间).考虑每个位置插入的$x$是$x_i$个.那么$\sum_{j=1}^{len-i+1}x_j=i,(x_j\geq0)$即不定方程非负整数解计数,做代换$y_i=x_i+1$转化成不定方程正整数解.$\sum_{j=1}^{len-i+1}y_j=i+len-i+1=len+1$.再次考虑组合意义,将$len+1$个完全一致的球排成一列,插入$len-i$个隔板(不能插入头尾,共len个位置可以插入),两两间至少有一个球,分成$len-i+1$组的方案计数.即为$\binom{len}{len-i}=\binom{len}{i}

上面的方程,让我们得到了O(n^3)的做法,观察方程里面一堆len-i,i感觉肯定有卷积.这时记住套路组合数拆成阶乘,看下标分配给不同项
具体地

f_{x,len}=\sum_{i=0}^{min(len,m)}\binom{len}{i}f_{x-1,len-i} f_{x,len}=\sum_{i=0}^{min(len,m)}\frac{len!}{i!(len-i)!}f_{x-1,len-i} \frac{f_{x,len}}{len!}=\sum_{i=0}^{min(len,m)}\frac{f_{x-1,len-i}}{(len-i)!}\frac{1}{i!} let\,F_x[len]=\frac{f_{x,len}}{len!}\quad G[i]=\frac{1}{i!},H[i]=G[i][i\leq m] F_x[len]=\sum_{i=0}^{min(len,m)}F_{x-1}[len-i]G[i]=\sum_{i=0}^{len}F_{x-1}[len-i]H[i] F_x=F_{x-1}*H

我们发现卷一次H就是批量转移一次,每次使用的H都一样,卷积即为多项式乘法,具有结合律,使用类似快速幂的倍增算法,可以在O(log\,n)次卷积内计算出答案,每次卷积我们使用NTT,即可得到O(nlog^2\,n)的解法.

代码如图

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cassert>
#include <ctime>
using namespace std;
typedef long long Int;
const int N=(1<<19);
const Int mod=998244353LL;
const Int G=3LL;
Int qpow(Int a,Int p){
    if(p==0) return 1;
    Int r=qpow(a,p>>1); r=r*r%mod;
    return (p&1)?(r*a%mod):r;
}
inline Int inv(Int a){ return qpow(a,mod-2); }
namespace Poly{
    const int CUTOFF=30;
    Int buf[CUTOFF];
    // 小技巧,即使你用的是递归的FFT,也能跑得过去.
    // 小范围暴力代替分治,减少了push/pop stack的开销
    // 是一个复杂度与常数之间的平衡.
    // 具体来说,dft即为带入求值...我们暴力平方复杂度带入即可.
    void fft(Int *A,int n,int f){
        Int base=qpow(G,(mod-1)/n),w=1,t=0;
        if(f<0) base=inv(base);
        if(n<CUTOFF){
            for(int i=0;i<n;i++){
                for(int j=n-1;j>=0;j--) t=(t*w%mod+A[j])%mod;
                buf[i]=t; t=0; w=w*base%mod;
            }
            for(int i=0;i<n;i++) A[i]=buf[i];
            return ;
        }
        int m=n>>1,p=0;
        Int *A0=new Int[m],*A1=new Int[m];
        for(int i=0;i<m;i++){ A0[i]=A[p++]; A1[i]=A[p++]; }
        fft(A0,m,f); fft(A1,m,f);
        for(int i=0;i<m;i++){
            t=w*A1[i]%mod;
            A[i]=(A0[i]+t)%mod;
            A[i+m]=(A0[i]-t+mod)%mod;
            w=w*base%mod;
        }
        delete[] A0; delete[] A1;
    }
    inline void trans(Int *A,int n,int f){
        fft(A,n,f);
        if(f<0){
            Int x=inv(n);
            for(int i=0;i<n;i++) A[i]=A[i]*x%mod;
        }
    }
}using Poly::trans;

// 多项式快速幂.modlen表示模x^p进行计算
// 显然不能保留整个多项式,我们发现只要每次保留一部分,后面的部分是不会影响转移的
// 形式化的说,我们在模x^p意义下进行多项式运算.
Int poly_qpow(Int *Poly,int modlen,int n,int at){
// 这个函数用于计算Poly 的n次方,模x^modlen意义下,x^at项的系数.
    int k=1; while(k<=modlen*2) k<<=1;
    for(int i=0;i<modlen;i++) base[i]=Poly[i];
    for(int i=modlen;i<k;i++) base[i]=0;
    for(int i=0;i<k;i++) ret[i]=0; ret[0]=1;

    while(n){
        if(n&1){
            trans(base,k,1); trans(ret,k,1);
            for(int i=0;i<k;i++) ret[i]=ret[i]*base[i]%mod;
            trans(base,k,-1); trans(ret,k,-1);
            for(int i=modlen;i<k;i++) ret[i]=0;
        }
        trans(base,k,1);
        for(int i=0;i<k;i++) base[i]=base[i]*base[i]%mod;
        trans(base,k,-1);
        for(int i=modlen;i<k;i++) base[i]=0;
        n>>=1;
    }
    return ret[at];
}
// 计算长度为len,元素为[1,n],每个元素出现次数不超过m的序列计数.
inline Int count(int len,int n,int m){
    if(m<=0) return 0;
    // 这个多项式B即为推导中的H
    for(int i=0;i<=m;i++) B[i]=ifac[i];
    for(int i=m+1;i<N;i++) B[i]=0;
    // 记得把阶乘补充回来.
    return poly_qpow(B,len+1,n,len)*fac[len]%mod;
}
int n,m;
int read(){
    int x=0;char c;
    do{c=getchar();}while(!isdigit(c));
    do{x=x*10+c-'0';c=getchar();}while(isdigit(c));
    return x;
}
int main(){
    n=read();m=read();
    ifac[0]=fac[0]=1;
    for(int i=1;i<N;i++) ifac[i]=inv(fac[i]=fac[i-1]*i%mod);

    Int ans=(count(n-2,n,m-1)-count(n-2,n,m-2)+mod)%mod;
    cout<<ans<<endl;
    return 0;
}

后记

即使你不会EGF,不知道各种图计数的操作.不懂多项式科技只会写一个fft板子也能轻松切题.

如果你会多项式exp,了解EGF和有标号图计数的各种玩法,这个就是板子了...显然作为一个懒人,我是只会fft板子和求逆的 更多玩法请自行查找NOI WC2019上"生成函数 多项式 图计数"的课件和策爷的集训队论文.

BJOI2019 RP++省选爆0稳了.