hdu4656 Evaluation NTT

非常好的推式子的题

用到了很多知识点

推式子，

先交换 i   j  目的是把K放到外面来

 后面先卷积预处理

得到p[j]

然后继续推式子

利用

得到

瞎卷一波就可以了。
注意一下    k−j   可能是负数，所以要倍长一下

要么三模数NTT，要么拆系数FFT

FFT   更快些   

#include <algorithm>
#include <cstdio>
#include <cstring>
#include<iostream>
using namespace std;
int mod=1e6+3;
typedef long long ll;
namespace Math
{
inline int pw(int base, int p, const int mod)
{
    static int res;
    for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
    return res;
}
inline int inv(int x, const int mod)
{
    return pw(x, mod - 2, mod);
}
}
long long qpow(long long a,long long n)
{
    long long ans=1;
    while(n)
    {
        if(n&1)
            ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
using namespace Math;
const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
const long long mod_1_2 = static_cast<long long> (mod1) * mod2;
const int inv_1 = Math::inv(mod1, mod2), inv_2 = Math::inv(mod_1_2 % mod3, mod3);
struct Int
{
    int A, B, C;
    explicit inline Int() { }
    explicit inline Int(int __num) : A(__num), B(__num), C(__num) { }
    explicit inline Int(int __A, int __B, int __C) : A(__A), B(__B), C(__C) { }
    static inline Int reduce(const Int &x)
    {
        return Int(x.A + (x.A >> 31 & mod1), x.B + (x.B >> 31 & mod2), x.C + (x.C >> 31 & mod3));
    }
    inline friend Int operator + (const Int &lhs, const Int &rhs)
    {
        return reduce(Int(lhs.A + rhs.A - mod1, lhs.B + rhs.B - mod2, lhs.C + rhs.C - mod3));
    }
    inline friend Int operator - (const Int &lhs, const Int &rhs)
    {
        return reduce(Int(lhs.A - rhs.A, lhs.B - rhs.B, lhs.C - rhs.C));
    }
    inline friend Int operator * (const Int &lhs, const Int &rhs)
    {
        return Int(static_cast<long long> (lhs.A) * rhs.A % mod1, static_cast<long long> (lhs.B) * rhs.B % mod2, static_cast<long long> (lhs.C) * rhs.C % mod3);
    }
    inline int get()
    {
        long long x = static_cast<long long> (B - A + mod2) % mod2 * inv_1 % mod2 * mod1 + A;
        return (static_cast<long long> (C - x % mod3 + mod3) % mod3 * inv_2 % mod3 * (mod_1_2 % mod) % mod + x) % mod;
    }
} ;

#define maxn 262144

namespace Poly
{
#define N (maxn << 1)
int lim, s, rev[N];
Int Wn[N | 1];
inline void init(int n)
{
    s = -1, lim = 1;
    while (lim < n) lim <<= 1, ++s;
    for (register int i = 1; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
    const Int t(Math::pw(G, (mod1 - 1) / lim, mod1), Math::pw(G, (mod2 - 1) / lim, mod2), Math::pw(G, (mod3 - 1) / lim, mod3));
    *Wn = Int(1);
    for (register Int *i = Wn; i != Wn + lim; ++i) *(i + 1) = *i * t;
}
inline void NTT(Int *A, const int op = 1)
{
    for (register int i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
    for (register int mid = 1; mid < lim; mid <<= 1)
    {
        const int t = lim / mid >> 1;
        for (register int i = 0; i < lim; i += mid << 1)
        {
            for (register int j = 0; j < mid; ++j)
            {
                const Int W = op ? Wn[t * j] : Wn[lim - t * j];
                const Int X = A[i + j], Y = A[i + j + mid] * W;
                A[i + j] = X + Y, A[i + j + mid] = X - Y;
            }
        }
    }
    if (!op)
    {
        const Int ilim(Math::inv(lim, mod1), Math::inv(lim, mod2), Math::inv(lim, mod3));
        for (register Int *i = A; i != A + lim; ++i) *i = (*i) * ilim;
    }
}
#undef N
}

using namespace Poly;
Int A[maxn << 1], B[maxn << 1],C[maxn << 1 ];
int N=(maxn-312);
ll fac[maxn];
ll ner[maxn];
int a[maxn];
ll temp[maxn];
ll p[maxn];
void f()
{
     lim=0, s=0;
     memset(rev,0,sizeof(rev));
     memset(Wn,0,sizeof(Wn));
     memset(A,0,sizeof(A));
     memset(B,0,sizeof(B));
}
ll c2[maxn];
int main()
{
    fac[0]=1;
    for(ll i=1; i<=N; i++)
        fac[i]=fac[i-1]*i%mod;
    ner[N]=pw(fac[N],mod-2,mod);
    for(ll i=N-1; i>=0; i--)
        ner[i]=(ner[i+1]*(i+1))%mod;
    ll n,b,c,d;
    scanf("%lld%lld%lld%lld",&n,&b,&c,&d);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    for (ll i = 0, x; i <=n; ++i)
    {
        temp[i] =a[n-i]*fac[n-i]%mod;
    }
    long long x=1;
    for (ll i = 0; i <=n; ++i)
    {
        B[i] =Int(ner[i]*x%mod);
        x=x*d%mod;
    }
    //reverse(temp,temp+1+n);
    for (ll i = 0, x; i <=n; ++i)
    {
        A[i]=Int(temp[i]);
    }
    init(n+n+2);
    NTT(A), NTT(B);
    for (ll i = 0; i < lim; ++i) A[i] = A[i] * B[i];
    NTT(A, 0);
    for (ll i = 0; i <=n; ++i)
    {
        p[n-i]=A[i].get();
    }

    f();
    x=1;
    for(ll i=0;i<maxn;i++)
    {
        c2[i]=qpow(c,(ll)i*i);
    }
    for (ll i = 0; i <=n; ++i)
    {
        A[i]=Int(x*c2[i]%mod*ner[i]%mod*p[i]%mod);
        x=x*b%mod;
    }
    for (ll i = 0; i <=n; ++i)
    {
        B[n-i]=B[n+i]=Int(qpow(c2[i],mod-2));
    }
    init(n+n*2+2);
    NTT(A), NTT(B);
    for (ll i = 0; i < lim; ++i) A[i] = A[i] * B[i];
    NTT(A, 0);
    for(ll i=0;i<n;i++)
    {
        printf("%lld\n",((A[n+i].get())%mod*c2[i]%mod)%mod);
    }
    return 0;
}