hdu_6061 RXD and functions

题目:

  RXD has a polynomial function ,
  RXD has a transformation of function , it returns another function , which has a property that .
  Given , RXD generates a polynomial function sequence , in which and
  RXD wants you to find , in the form of
  You need to output bi module .
  

思路:

  其实题目所求的就是 展开后的式子。先考虑把 展开,得到:,设 ,把这个式子二项式展开,得到:。关于 的式子可以先不管它(最后处理),把所有 分别提到两个多项式中(因为这两个值相加正好是 ),也就是 。因为模数有原根,所以用NTT把这两个式子乘在一起就行了。得到的系数再乘以 。复杂度

代码:

#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define _(...) (void)(__VA_ARGS__)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int MOD=998244353,N=131072*2+5;

int qkpow(int x,int k){
    int ans=1;
    for(;k;k>>=1,x=(ll)x*x%MOD)
        if(k&1)ans=(ll)x*ans%MOD;
    return ans;
}
int inv(int x){
    return qkpow(x,MOD-2);
}

int rev[N],s;
    void dft(int a[],int n,bool inv_f){
    rep(i,0,n-1)
        if(rev[i]<i)
            std::swap(a[i],a[rev[i]]);
    for(int l=2,m=1;l<=n;l<<=1,m<<=1){
        int base=qkpow(3,(MOD-1)/l);
        if(inv_f)base=inv(base);
        for(int *p=a;p!=a+n;p+=l){
            int w=1;
            rep(i,0,m-1){
                int t=(ll)w*p[i+m]%MOD;
                p[i+m]=(p[i]-t+MOD)%MOD;
                p[i]=(p[i]+t)%MOD;
                w=(ll)w*base%MOD;
            }
        }
    }
    int invn=inv(n);
    if(inv_f)
        rep(i,0,n-1)
            a[i]=(ll)a[i]*invn%MOD;
}

int log2(int x){
    int lim=0;
    while((1<<lim)<x)lim++;
    return lim;
}

int fac[N],ifac[N];
void init(){
    int n=N-5;
    fac[0]=1;
    rep(i,1,n)
        fac[i]=(ll)fac[i-1]*i%MOD;
    ifac[n]=inv(fac[n]);
    drep(i,n-1,0)
        ifac[i]=(ll)ifac[i+1]*(i+1)%MOD;
}

int a[N],b[N],c[N],n,m;
void input(){
    rep(i,0,n)
        scanf("%d",c+i);
    scanf("%d",&m);
    s=0;
    rep(i,1,m){
        int v;
        scanf("%d",&v);
        s=(s+v)%MOD;
    }
}

int main(){
    init();
    while(~scanf("%d",&n)){
        input();

        mset(a,0);mset(b,0);
        rep(i,0,n)
            a[i]=(ll)c[i]*fac[i]%MOD;
        s=(-s+MOD)%MOD;
        rep(i,0,n)
            b[n-i]=(ll)qkpow(s,i)*ifac[i]%MOD;

        int lim=log2(n*2+2),d=1<<lim;
        rep(i,0,d-1)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));

        dft(a,d,false);dft(b,d,false);
        rep(i,0,d-1)
            a[i]=(ll)a[i]*b[i]%MOD;
        dft(a,d,true);

        rep(i,n,2*n)
            printf("%lld ",(ll)a[i]*ifac[i-n]%MOD);
        puts("");
    }
    return 0;
}