2017多校訓練賽第三場 HDU 6061（NTT模闆）

RXD and functions

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Total Submission(s): 820    Accepted Submission(s): 335

Problem Description

RXD has a polynomial function f(x),f(x)=∑ni=0cixi

RXD has a transformation of function Tr(f,a), it returns another function g, which has a property that g(x)=f(x−a).

Given a1,a2,a3,…,am, RXD generates a polynomial function sequence gi, in which g0=f and gi=Tr(gi−1,ai)

RXD wants you to find gm, in the form of ∑mi=0bixi

You need to output bi module 998244353.

n≤105

Input

There are several test cases, please keep reading until EOF.

For each test case, the first line consists of 1 integer n, which means degF.

The next line consists of n+1 intergers ci,0≤ci<998244353, which means the coefficient of the polynomial.

The next line contains an integer m, which means the length of a.

The next line contains m integers, the i - th integer is ai.

There are 11 test cases.

0<=ai<998244353

∑m≤105

Output

For each test case, output an polynomial with degree n, which means the answer.

Sample Input

2

0 0 1

1

1

Sample Output

Hint

Source

​​2017 Multi-University Training Contest - Team 3​​

        題目容易了解，相當于求f(x-sigma(ai))。

#include<bits/stdc++.h>
#define mod 998244353
#define LL long long
#define N 100010
#define g 3
using namespace std;

namespace NTT
{
    int x[N<<2],y[N<<2],wn[N<<2];

    int qpow(int a,int b)
    {
        int ans=1;
        while(b)
        {
            if(b&1)ans=(LL)ans*a%mod;
            a=(LL)a*a%mod;
            b>>=1;
        }
        return ans;
    }

    void init()
    {
        for(int i=0;i<21;i++)
        {
            int t=1<<i;
            wn[i]=qpow(g,(mod-1)/t);
        }
    }

    void brc(int *F,int len)
    {
        int j=len/2;
        for(int i=1;i<len-1;i++)
        {
            if(i<j)swap(F[i],F[j]);
            int k=len/2;
            while(j>=k)
            {
                j-=k;
                k>>=1;
            }
            if(j<k)j+=k;
        }
    }
    void NTT(int *F,int len,int t)
    {
        int id=0;
        brc(F,len);
        for(int h=2;h<=len;h<<=1)
        {
            id++;
            for(int j=0;j<len;j+=h)
            {
                int E=1;
                for(int k=j;k<j+h/2;k++)
                {
                    int u=F[k];
                    int v=(LL)E*F[k+h/2]%mod;
                    F[k]=(u+v)%mod;
                    F[k+h/2]=((u-v)%mod+mod)%mod;
                    E=(LL)E*wn[id]%mod;
                }
            }
        }
        if(t==-1)
        {
            for(int i=1;i<len/2;i++)swap(F[i],F[len-i]);
            LL inv=qpow(len,mod-2);
            for(int i=0;i<len;i++)F[i]=(LL)F[i]%mod*inv%mod;
        }
    }

    void multiply(int *a,int len1,int *b,int len2)
    {
        int len=1;
        while(len<len1+len2)len<<=1;
        for (int i = len1; i < len; i++) a[i] = 0;
        for (int i = len2; i < len; i++) b[i] = 0;
        NTT(a,len,1); NTT(b,len,1);
        for(int i=0;i<len;i++)
            a[i]=(LL)a[i]*b[i]%mod;
        NTT(a,len,-1);
    }
}

int fac[N],inv[N],c[N];
int n,m;

void init()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<N;i++)
    {
        fac[i] =(LL)fac[i-1] * i % mod;
        inv[i]=mod-(int)(mod/i*(LL)inv[mod%i]%mod);                //線性求i的逆元
    }
    for(int i=1;i<N;i++)
        inv[i]=(LL)inv[i-1]*inv[i]%mod;
}

int main()
{
    init();
    NTT::init();
    while(~scanf("%d",&n))
    {
        int sum=0;
        for(int i=0;i<=n;i++)
            scanf("%d",&c[i]);
        scanf("%d",&m);
        while(m--)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            if (sum>=mod) sum-=mod;
        }
        int x=1; NTT::y[0]=1;
        for(int i=0;i<=n;i++)
            NTT::x[i]=(LL)c[n-i]*fac[n-i]%mod;
        for(int i=1;i<=n;i++)
        {
            x=(LL)x*sum%mod; x=mod-x;
            NTT::y[i]=(LL)x*inv[i]%mod;
        }
        NTT::multiply(NTT::x,n+1,NTT::y,n+1);
        for(int i=0;i<=n;i++)
            NTT::x[i]=(LL)NTT::x[i]*inv[n-i]%mod;
        for(int i=0;i<=n;i++)
            printf("%d ",NTT::x[n-i]);
        puts("");
    }
    return 0;
}