[XSY2730] Ball 다항식exp 다항식ln 다항식 개근 상계수 선형 점차적 DP

제목의 대의.

한 줄에 n개의 공이 있는데, 지금 이 공들을 k조로 나누면, 각 조는 한 개의 공이 있거나 두 개의 공이 인접할 수 있다.한 구는 여러 그룹에만 있을 수 있습니다(어떤 그룹에도 없을 수 있습니다).1≤k≤m의 모든 k에 대해 각각 몇 가지 조를 나누는 방법이 있는지 구합니다.
답안은 998244353에 대한 모범을 취한다.
　　 n≤109,m<219

문제풀이

k>n의 항목은 모두 0이기 때문에 우리는 m≤n을 흠정한다
DP를 고려합니다.
f, j는 전 i개의 공을 j조로 나누는 방안 수를 기록한다.
fi,j=fi−1,j+fi−1,j−1+fi−2,j−1
직접 하다
O(nm)의.
만약fi를 다항식으로 간주한다면
Fi(x)=∑j≥0fi,jxj
그럼 옮기면 돼요.
Fi(x)=(1+x)Fi−1(x)+xFi−2(x)
이것은 상계수 일차선형 추이로 FFT 최적화로 할 수 있다
O(mlogmlogn)
상계수 일차선형 추이 관계의 통항 공식을 어떻게 구하는지 고려하다.
먼저 이 이동 행렬의 특징 다항식을 구하십시오:
λ2−(1+x)λ−x
피쳐 값은 다음과 같습니다.
λ1λ2=1+x+x2+6x+1‾‾‾‾‾‾‾‾‾‾‾√2=1+x−x2+6x+1‾‾‾‾‾‾‾‾‾‾‾√2
우리 흠정
F -3 1(x) = 0, 설정
Fi(x)=c1λ1i+1+c2λ2i+1
데리고 들어가다
F -3 1 (x), F0 (x)
{c1c2λ1+c2+c2λ2=0=1
이해할 수 있다
{c1c2=1λ1−λ2=1λ2−λ1
그리하여
Fi(x)=λ1i+1−λ2i+1λ1−λ2
직접 다항식 개근으로 구하다
λ1,λ2, 그리고 다항식
lnexp 구출
Fn(x)
시간 복잡도: O(mlogm)
작은 최적화: 왜냐하면 [x0]λ그래서λ2의 전 n+1항은 모두 0이다.m≤n 때문에
λ2n+1≡0(modxm+1)
그래서 저희가 계산을 안 해도 돼요.
λ2n+1이야.

코드

#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=300000;
const ll p=998244353;
const ll g=3;
const ll inv2=(p+1)/2;
ll fp(ll a,ll b)
{
    ll s=1;
    for(;b;b>>=1,a=a*a%p)
        if(b&1)
            s=s*a%p;
    return s;
}
int rev[maxn];
ll w1[maxn];
ll w2[maxn];
void ntt(ll *a,int n,int t)
{
    int i,j,k;
    ll u,v,w,wn;
    for(i=1;i>1]>>1)|(i&1?n>>1:0);
        if(rev[i]>i)
            swap(a[i],a[rev[i]]);
    }
    for(i=2;i<=n;i<<=1)
    {
        wn=(t==1?w1[i]:w2[i]);
        for(j=0;j1;
            for(k=j;k2;k++)
            {
                u=a[k];
                v=a[k+i/2]*w%p;
                a[k]=(u+v)%p;
                a[k+i/2]=(u-v)%p;
                w=w*wn%p;
            }
        }
    }
    if(t==-1)
    {
        ll inv=fp(n,p-2);
        for(i=0;i*inv%p;
    }
}
void getinv(ll *a,ll *b,int n)
{
    if(n==1)
    {
        b[0]=fp(a[0],p-2);
        return;
    }
    getinv(a,b,n>>1);
    static ll a1[maxn],a2[maxn];
    int i;
    for(i=0;ifor(;i1;i++)
        a1[i]=0;
    for(i=0;i>1;i++)
        a2[i]=b[i];
    for(;i1;i++)
        a2[i]=0;
    ntt(a1,n<<1,1);
    ntt(a2,n<<1,1);
    for(i=0;i1;i++)
        a1[i]=a2[i]*((2-a1[i]*a2[i])%p)%p;
    ntt(a1,n<<1,-1);
    for(i=0;i*a,ll *b,int n)
{
    if(n==1)
    {
        b[0]=1;
        return;
    }
    getsqrt(a,b,n>>1);
    static ll a1[maxn],a2[maxn],a3[maxn];
    int i;
    for(i=0;i>1;i++)
        a1[i]=b[i];
    for(;i1;i++)
        a1[i]=0;
    for(i=0;ifor(;i1;i++)
        a2[i]=0;
    getinv(a1,a3,n);
    ntt(a2,n<<1,1);
    ntt(a3,n<<1,1);
    for(i=0;i1;i++)
        a2[i]=a2[i]*a3[i]%p;
    ntt(a2,n<<1,-1);
    for(i=0;i%p*inv2%p;
}
void getln(ll *a,ll *b,int n)
{
    static ll inv[maxn],a1[maxn],a2[maxn];
    int i;
    inv[0]=inv[1]=1;
    for(i=2;i*inv[p%i]%p;
    for(i=1;i1]=a[i]*i%p;
    a1[n-1]=0;
    getinv(a,a2,n);
    for(i=n;i1;i++)
        a1[i]=a2[i]=0;
    ntt(a1,n<<1,1);
    ntt(a2,n<<1,1);
    for(i=0;i1;i++)
        a1[i]=a1[i]*a2[i]%p;
    ntt(a1,n<<1,-1);
    for(i=1;i1]*inv[i]%p;
    b[0]=0;
}
void getexp(ll *a,ll *b,int n)
{
    if(n==1)
    {
        b[0]=1;
        return;
    }
    getexp(a,b,n>>1);
    int i;
    for(i=n>>1;i0;
    static ll a1[maxn],a2[maxn],a3[maxn];
    getln(b,a1,n);
    for(i=0;i>1;i++)
    {
        a2[i]=b[i];
        a3[i]=a[i+(n>>1)]-a1[i+(n>>1)];
    }
    for(;i0;
    ntt(a2,n,1);
    ntt(a3,n,1);
    for(i=0;i*a3[i]%p;
    ntt(a2,n,-1);
    for(i=0;i>1;i++)
        b[i+(n>>1)]=a2[i];
}
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll d[maxn];
ll e[maxn];
int n,m;
int k;
void solve()
{
    k=1;
    while(k<=m)
        k<<=1;
    int i;
    for(i=2;i<=k<<1;i++)
    {
        w1[i]=fp(g,(p-1)/i);
        w2[i]=fp(w1[i],p-2);
    }
    d[0]=1;
    d[1]=6;
    d[2]=1;
    getsqrt(d,c,k);
    for(i=0;i0]++;
    a[1]++;
    for(i=0;i*inv2%p;
    getinv(c,b,k);
    getln(a,e,k);
    for(i=0;i*(n+1)%p;
    getexp(e,a,k);
    for(i=k;i1;i++)
        a[i]=b[i]=0;
    ntt(a,k<<1,1);
    ntt(b,k<<1,1);
    for(i=0;i1;i++)
        a[i]=a[i]*b[i]%p;
    ntt(a,k<<1,-1);
    for(i=1;i<=m;i++)
    {
        a[i]=(a[i]+p)%p;
        printf("%lld ",a[i]);
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
#endif
    int x=0;
    scanf("%d%d",&n,&m);
    if(m>n)
    {
        x=m-n;
        m=n;
    }
    solve();
    while(x--)
        printf("0 ");
    return 0;
}