题目概述

HDU7199

解题报告

多项式套路题，需要把题目中两种路径对应到比较容易处理的多项式形式。

首先是 $i\to i+1$ ，有 $n+k-i$ 条路径，这个形式不太友好，因此我们考虑把整个序列反过来，即 $i$ 点变为 $n+k-i$ 点，这样就变成了 $i\to i-1$ 有 $i$ 条路径，就和下标对应起来了。翻转过后，第二种路径就变成了 $i\to i+x$ 有 $a_x$ 条路径。

接下来考虑每轮的转移，定义 $f_{i,j}$ 表示走了 $i$ 步，停在 $j$ 的方案数（初值 $f_{0,n-1}=1$ ），那么：

$$ f_{i,j}=(j+1)f_{i-1,j+1}+\sum_{x=1}^{n-1}a_xf_{i-1,k-x}=(j+1)f_{i-1,j+1}+\sum_{k=0}^{j-1}a_{j-k}f_{i-1,k} $$

后面是卷积形式，而前面由于我们已经把下标和权值对应了，因此不难发现如果用多项式表示，这是求导的过程。

定义 $F_i(x)$ 为 $f_{i}$ 的生成函数，令 $A(x)=\sum_{i=1}^{n-1}a_ix^i$ ，那么：

$$ F_i(x)=F_{i-1}'(x)+A(x)F_{i-1}(x) $$

这个形式让我们想到构造 $P_i(x)=e^{G(x)}F_i(x)$ ，因为：

$$ P_i'(x)=e^{G(x)}G'(x)F_i(x)+e^{G(x)}F_i'(x)=e^{G(x)}[F_i'(x)+G'(x)F_i(x)] $$

因此如果让 $G'(x)=A(x),G(x)=\int A(x)dx$ 就可以让后面出现 $F_i'(x)+A(x)F_i(x)$ ，从而：

$$ P_i'(x)=e^{G(x)}[F_i'(x)+A(x)F_i(x)]=e^{G(x)}F_{i+1}(x)=P_{i+1}(x) $$

这样我们只要求出 $P_0(x)=e^{G(x)}F_0(x)=x^{n-1}e^{G(x)}$ ，然后求 $k$ 阶导就可以得到 $P_k(x)$ ，最后 $F_k(x)={P_k(x)\over e^{G(x)}}$ 。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxt=1<<20,MOD=998244353;

int te,n,K,A[maxt+5];
int fac[maxt+5],INV[maxt+5];
int wn[maxt+5],tem[maxt+5],G[maxt+5],P[maxt+5],F[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[100000];
    fastO() {si=0;}
    void putc(char ch){
        if (si==100000) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    int len=0,buf[100];
    if (x<0) fo.putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    fo.putc(ch);
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt/2]=1;
    for (int i=maxt/2+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=maxt/2-1;i>=0;i--) wn[i]=wn[i<<1];
}
void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(a[i+j],y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Inte(int *F,int *a,int n,int K){ // F=integral(a)
    for (int i=n+K;i>=K;i--) F[i]=MUL(a[i-K],MUL(INV[i],fac[i-K]));
    for (int i=0;i<K;i++) F[i]=0;
}
void Deri(int *F,int *a,int n,int K){ // F=a'
    for (int i=0;i<=n-K;i++) F[i]=MUL(a[i+K],MUL(fac[i+K],INV[i]));
    for (int i=n-K+1;i<=n;i++) F[i]=0;
}
void Inv(int *F,int *a,int n){ // F=1/a
    if (n==1) {F[0]=Pow(a[0],MOD-2);return;}
    Inv(F,a,n>>1);
    for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=F[i+n]=0;
    NTT(tem,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=MUL(F[i],2+MOD-MUL(tem[i],F[i]));
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0;
}
void Ln(int *F,int *a,int n){ // F=ln(a)
    static int A[maxt+5],B[maxt+5];
    Deri(A,a,n-1,1);for (int i=0;i<n;i++) A[i+n]=0;
    Inv(B,a,n);NTT(A,n<<1,1);NTT(B,n<<1,1);
    for (int i=0;i<(n<<1);i++) B[i]=MUL(A[i],B[i]);
    NTT(B,n<<1,-1);Inte(F,B,n-2,1);
}
void Exp(int *F,int *a,int n){ // F=exp(a)
    if (n==1) {F[0]=1;return;}
    Exp(F,a,n>>1);Ln(tem,F,n);
    for (int i=0;i<n;i++) tem[i]=ADD(a[i],MOD-tem[i]),tem[i+n]=F[i+n]=0;tem[0]=ADD(tem[0],1);
    NTT(tem,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=MUL(tem[i],F[i]);
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0;
}
int main(){
    NTTPre();Make(maxt);
    for (readi(te);te;te--){
        readi(n);readi(K);
        int t;for (t=1;t<=n+K-1;t<<=1);
        A[0]=0;for (int i=1;i<n;i++) readi(A[i]);
        Inte(A,A,n-1,1);for (int i=n+1;i<t;i++) A[i]=0;
        Exp(G,A,t);
        for (int i=n-1;i<=n+K-1;i++) P[i]=G[i-(n-1)];
        for (int i=0;i<n-1;i++) P[i]=0;
        Deri(P,P,n+K-1,K);
        int s;for (s=1;s<=(n-1<<1);s<<=1);
        for (int i=n;i<s;i++) P[i]=0;
        for (int i=t;i<s;i++) G[i]=0;
        NTT(P,s,1);Inv(F,G,s>>1);NTT(F,s,1);
        for (int i=0;i<s;i++) F[i]=MUL(F[i],P[i]);
        NTT(F,s,-1);
        for (int i=n-1;i>=0;i--) writei(F[i],i>0?' ':'\n');
    }
    return 0;
}