ZJT's Blog

Keep your determination.

扩展拉格朗日反演

2018-3-4 9:432018-4-6 16:8
拉格朗日反演FFT生成函数

突然发现拉格朗日反演其实还有扩展的形式。。。

定义$F^{-1}$为$F$的复合逆:

$$ F^{-1}(F(x))=x $$

$$[x^n]G(F^{-1}(x))=\frac1n[x^{-1}] ( \frac{dG(x)}{dx}\frac1{F^n(x)})$$

(这个好像叫Lagrange–Bürmann formula

注意一般$G$的表达式都同时含有$x$和$F^{-1}(x)$,我们把$F(x)$代入$x$后就能得到$G(x)$的表达式,进而求出$\frac {dG(x)}{dx}$。

感觉还是蛮有用的(大雾)

查看详细内容

[自选题 #120] Mike学OI

2018-1-4 20:442018-1-4 20:44
集训队作业自选题生成函数FFT

传送门

多项式多点插值+多点求值的模板题。

不过之前一直以为插值是$O(n\log^3n)$的,直到这题solution给了一个两个log的做法。插值的瓶颈在于求出$g_i=\prod_{i\ne j}(x_i-x_j)$,我们可以把他表示成$f(x)=\frac{\prod{x-x_j}}{x-x_i}$在$x=x_i$处的极限。根据洛必达法则,我们对分式上下求导,得到$\lim_{x\to x_i}f(x)=(\prod(x-x_j))'|_{x=x_i}$。也就是说,我们先分治算出$\prod(x-x_j)$,然后再把这个多项式求导,并在所有$x_i$处多点求值一下,就能得到所有的$g_i$。得到$g_i$之后就好办了,代到拉格朗日插值的式子里面,随便分治一下就出来了。

好久没写这种东西了,代码写的很乱。。。感觉要调整一下写法了。

#include <bits/stdc++.h>
#define LL long long
#define MAXN 270000
#define MAXW 262144
#define B 600
using namespace std;

const LL P=998244353;
LL w[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

struct Poly{
    LL a[MAXN];
    int len;
    inline LL &operator[](int i){ return a[i]; }
    void reset(int _len){ len=_len; memset(a,0,(len+1)*sizeof(LL)); }
};

void FFT(Poly &a,int len,int flag){
    static int rev[MAXN],revlen;
    if(revlen!=len){
        revlen=len;
        for(int i=1;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
    }
    for(int i=0;i<len;i++) if(i<rev[i]) swap(a.a[i],a.a[rev[i]]);
    for(int l=2;l<=len;l<<=1){
        int l2=l>>1;
        for(int i=0;i<len;i+=l){
            for(int j=0;j<l2;j++){
                LL t1=a.a[i+j],t2=a.a[i+j+l2]*w[MAXW/l*j];
                a.a[i+j]=(t1+t2)%P;
                a.a[i+j+l2]=(t1-t2)%P;
            }
        }
    }
    if(flag==-1){
        LL invn=getPow(len,P-2);
        for(int i=0;i<len;i++) a.a[i]=a.a[i]*invn%P;
        for(int i=1;i<len;i++) if(i<len-i) swap(a.a[i],a.a[len-i]);
    }
}

void getMul(Poly &a,Poly &b,Poly &c){
    int sizew=1;
    while(sizew<=a.len+b.len) sizew<<=1;
    sizew<<=1;
    static Poly t1,t2;
    t1.reset(sizew); t2.reset(sizew);
    for(int i=0;i<=a.len;i++) t1[i]=a[i];
    for(int i=0;i<=b.len;i++) t2[i]=b[i];
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,sizew,-1);
    c.len=a.len+b.len;
    for(int i=0;i<=c.len;i++) c[i]=t1[i];
}

void getInv(Poly &b,Poly &a,int len=-1){
    if(len==-1) for(len=1;len<=a.len;len<<=1);
    if(len==1){
        b.len=len;
        b[0]=getPow(a[0],P-2);
        return;
    }
    static Poly t1,t2;
    getInv(t1,a,len>>1);
    for(int i=len>>1;i<len<<1;i++) t1[i]=0;
    t2.reset((len<<1)-1);
    for(int i=0;i<len;i++) t2[i]=a[i];
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<len<<1;i++) t1[i]=(2*t1[i]-t2[i]*t1[i]%P*t1[i])%P;
    FFT(t1,len<<1,-1);
    b.len=len-1;
    for(int i=0;i<len;i++) b[i]=t1[i];
}

void reverse(Poly &a){
    for(int i=0;i<=a.len;i++) if(i<a.len-i) swap(a[i],a[a.len-i]);
}

void getMod(Poly &a,Poly &b,Poly &c){
    if(a.len<b.len){
        c.len=a.len;
        for(int i=0;i<=a.len;i++) c[i]=a[i];
        return;
    }
    static Poly t1,t2,t3,t4;
    t1.len=a.len; for(int i=0;i<=a.len;i++) t1[i]=a[i];
    t2.len=b.len; for(int i=0;i<=b.len;i++) t2[i]=b[i];
    reverse(t1); reverse(t2);
    while(t2.len<a.len-b.len) t2[++t2.len]=0;
    t2.len=a.len-b.len;
    getInv(t4,t2);
    while(t1.len<a.len-b.len) t1[++t1.len]=0;
    while(t4.len<a.len-b.len) t4[++t4.len]=0;
    t1.len=t4.len=a.len-b.len;
    getMul(t1,t4,t3); t3.len=a.len-b.len;
    t2.len=b.len; getMul(t3,t2,t2);
    int lenc=b.len-1;
    c.len=a.len;
    for(int i=0;i<=a.len;i++) c[i]=t1[i]-t2[i];
    reverse(c);
    c.len=lenc;
}

LL *xp[MAXN],*fp[MAXN];

void getXP(int id,LL *x,int len){
    if(len==1){
        xp[id]=new LL[2];
        xp[id][0]=-x[0];
        xp[id][1]=1;
        fp[id]=new LL[2];
        return;
    }
    int mid=len>>1;
    getXP(id<<1,x,mid);
    getXP(id<<1|1,x+mid,len-mid);
    static Poly t1,t2;
    t1.len=mid; t2.len=len-mid;
    for(int i=0;i<=mid;i++) t1[i]=xp[id<<1][i];
    for(int i=0;i<=len-mid;i++) t2[i]=xp[id<<1|1][i];
    getMul(t1,t2,t1);
    xp[id]=new LL[len+1];
    fp[id]=new LL[len+1];
    for(int i=0;i<=len;i++) xp[id][i]=t1[i];
}

void getV(int id,LL *x,LL *y,int len){
    if(len<=B){
        for(int i=0;i<len;i++){
            LL res=0,temp=1;
            for(int j=0;j<=len;j++)
                res=(res+temp*fp[id][j])%P,temp=temp*x[i]%P;
            y[i]=res;
        }
        return;
    }
    int mid=len>>1;
    static Poly tp,t1,t2;
    t1.len=len;
    for(int i=0;i<=len;i++) t1[i]=fp[id][i];
    tp.len=mid;
    for(int i=0;i<=tp.len;i++) tp[i]=xp[id<<1][i];
    getMod(t1,tp,t2);
    for(int i=0;i<=mid;i++) fp[id<<1][i]=t2[i];
    tp.len=len-mid;
    for(int i=0;i<=tp.len;i++) tp[i]=xp[id<<1|1][i];
    getMod(t1,tp,t2);
    for(int i=0;i<=mid;i++) fp[id<<1|1][i]=t2[i];
    getV(id<<1,x,y,mid);
    getV(id<<1|1,x+mid,y+mid,len-mid);
}

void getV(Poly &a,LL *x,LL *y,int len){
    getXP(1,x,len);
    static Poly t1;
    t1.len=len;
    for(int i=0;i<=len;i++) t1[i]=xp[1][i];
    getMod(a,t1,t1);
    for(int i=0;i<=t1.len;i++) fp[1][i]=t1[i];
    for(int i=t1.len+1;i<=len;i++) fp[1][i]=0;
    getV(1,x,y,len);
}

void getPoly(int id,LL *x,LL *y,int len){
    if(len<=B){
        for(int i=0;i<=len;i++) fp[id][i]=0;
        for(int i=0;i<len;i++){
            LL last=0;
            for(int j=len;j;j--){
                LL temp=(xp[id][j]+last)%P;
                last=temp*x[i]%P;
                fp[id][j-1]=(fp[id][j-1]+temp*y[i])%P;
            }
        }
        return;
    }
    int mid=len>>1;
    getPoly(id<<1,x,y,mid);
    getPoly(id<<1|1,x+mid,y+mid,len-mid);
    static Poly t1,t2;
    t1.len=mid; for(int i=0;i<=t1.len;i++) t1[i]=fp[id<<1][i];
    t2.len=len-mid; for(int i=0;i<=t2.len;i++) t2[i]=xp[id<<1|1][i];
    getMul(t1,t2,t1);
    for(int i=0;i<=len;i++) fp[id][i]=t1[i];
    t1.len=len-mid; for(int i=0;i<=t1.len;i++) t1[i]=fp[id<<1|1][i];
    t2.len=mid; for(int i=0;i<=t2.len;i++) t2[i]=xp[id<<1][i];
    getMul(t1,t2,t1);
    for(int i=0;i<=len;i++) fp[id][i]=(fp[id][i]+t1[i])%P;
}

void getPoly(LL *x,LL *y,Poly &f,int len){
    getXP(1,x,len);
    static Poly py;
    static LL yv[MAXN];
    py.len=len;
    for(int i=0;i<=len;i++) py[i]=xp[1][i];
    for(int i=0;i<len;i++) fp[1][i]=py[i+1]*(i+1)%P;
    fp[1][len]=0;
    getV(1,x,yv,len);
    for(int i=0;i<len;i++) yv[i]=y[i]*getPow(yv[i],P-2)%P;
    getPoly(1,x,yv,len);
    for(int i=0;i<=len;i++) f[i]=fp[1][i];
    f.len=len;
}

void init(){
    w[1]=getPow(3,(P-1)/MAXW);
    w[0]=1;
    for(int i=2;i<MAXW;i++) w[i]=w[i-1]*w[1]%P;
}

void gao(){
    int n,m;
    static LL xv[MAXN],yv[MAXN];
    static Poly f;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lld%lld",xv+i,yv+i);
    getPoly(xv,yv,f,n);
    scanf("%d",&m);
    for(int i=0;i<m;i++) scanf("%lld",xv+i);
    getV(f,xv,yv,m);
    for(int i=0;i<m;i++) printf("%lld ",(yv[i]%P+P)%P);
}

int main(){
#ifdef DEBUG
    freopen("120.in","r",stdin);
#endif
    init();
    gao();
}

查看详细内容

[自选题 #127] Ball

2018-1-2 12:212018-1-2 12:22
集训队作业自选题生成函数FFT线性递推

传送门

考虑DP:$f_{i,j}$表示$i$个球分$j$组的方案数。显然$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}+f_{i-2,j-1}$。

如果我们把$f_i$看成一个$x$多项式,则$f_i(x)=(x+1)f_{i-1}(x)+xf_{i-2}(x)$。这是个常系数线性递推,特征方程为$\lambda^2-(x+1)\lambda-x=0$,解出特征根为$\lambda_1=\frac{x+1+\sqrt{x^2+6x+1}}{2},\lambda_2=\frac{x+1-\sqrt{x^2+6x+1}}{2}$。

我们钦定$f_{-1}(x)=0$,此时转移方程在所有正整数处都成立。我们设$f_i(x)=c_1(x)\lambda_1^{i+1}(x)+c_2(x)\lambda_2^{i+1}(x)$,把$f_{-1},f_0$代进去,得到$c_1=\frac 1{\lambda_1-\lambda_2},c_2=\frac 1{\lambda_2-\lambda_1}$。所以$f_n$就能表示成:$$f_n(x)=\frac {\lambda_1^{n+1}(x)-\lambda_2^{n+1}(x)}{\lambda_1(x)-\lambda_2(x)}$$

直接开根把$\lambda$算出来之后$\ln+\exp$求幂再求逆就行了。

由于$m\leq n$(当$m>n$时后面那些显然就是$0$),而$\lambda_2$的常数项是$0$,所以$\lambda_2^{n+1}(x)\equiv 0\pmod {x^{m+1}}$,这意味着分子后面那项根本没有贡献,可以直接忽略,从而减小常数。

#include <bits/stdc++.h>
#define MAXN 1100000
#define MAXW 1048576
#define LL long long 
using namespace std;

const LL P=998244353;

int n,m,sizew;
LL w[MAXW],inv_v[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

void init(){
    w[0]=1;
    w[1]=getPow(3,(P-1)/MAXW);
    for(int i=2;i<MAXW;i++) w[i]=w[i-1]*w[1]%P;
    inv_v[1]=1;
    for(int i=2;i<MAXN;i++)
        inv_v[i]=-inv_v[P%i]*(P/i)%P;
}

void FFT(LL *a,int n,int flag){
    static int rev[MAXN],revn;
    if(revn!=n){
        revn=n;
        for(int i=1;i<n;i++) rev[i]=rev[i>>1]>>1|((i&1)?(n>>1):0);
    }
    for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int l=2;l<=n;l<<=1){
        int l2=l>>1;
        for(int i=0;i<n;i+=l){
            for(int j=0;j<l2;j++){
                LL t1=a[i+j],t2=a[i+j+l2]*w[MAXW/l*j];
                a[i+j]=(t1+t2)%P;
                a[i+j+l2]=(t1-t2)%P;
            }
        }
    }
    if(flag==-1){
        LL invn=getPow(n,P-2);
        for(int i=0;i<n;i++) a[i]=a[i]*invn%P;
        for(int i=1;i<n;i++) if(i<n-i) swap(a[i],a[n-i]);
    }
}

void getInv(LL *b,LL *a,int len){
    if(len==1){
        b[0]=getPow(a[0],P-2);
        return;
    }
    static LL t1[MAXN],t2[MAXN];
    getInv(t1,a,len>>1);
    for(int i=len>>1;i<len<<1;i++) t1[i]=t2[i]=0;
    for(int i=0;i<len;i++) t2[i]=a[i];
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<len<<1;i++) t1[i]=(2*t1[i]-t2[i]*t1[i]%P*t1[i])%P;
    FFT(t1,len<<1,-1);
    for(int i=0;i<len;i++) b[i]=t1[i];
}

void getLn(LL *b,LL *a,int len){
    static LL t1[MAXN],t2[MAXN];
    for(int i=0;i<len;i++) t1[i]=a[i+1]*(i+1)%P,t2[i]=a[i];
    t1[len-1]=0;
    getInv(t2,t2,len);
    for(int i=0;i<len;i++) t1[i+len]=t2[i+len]=0;
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<len<<1;i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,len<<1,-1);
    for(int i=1;i<len;i++) b[i]=t1[i-1]*inv_v[i]%P;
    b[0]=0;
}

void getExp(LL *b,LL *a,int len){
    if(len==1){
        b[0]=1;
        return;
    }
    static LL t1[MAXN],t2[MAXN],t3[MAXN];
    getExp(t1,a,len>>1);
    for(int i=0;i<len>>1;i++) t3[i]=t1[i],t1[i+(len>>1)]=t3[i+(len>>1)]=0;
    getLn(t2,t1,len);
    for(int i=0;i<len>>1;i++) t2[i]=t2[i+(len>>1)]-a[i+(len>>1)],t2[i+(len>>1)]=0;
    FFT(t3,len,1); FFT(t2,len,1);
    for(int i=0;i<len;i++) t3[i]=t3[i]*t2[i]%P;
    FFT(t3,len,-1);
    for(int i=0;i<len>>1;i++) b[i]=t1[i],b[i+(len>>1)]=-t3[i];
}

void getPow(LL *b,LL *a,int len,LL k){
    static LL t1[MAXN];
    getLn(t1,a,len);
    for(int i=0;i<len;i++) t1[i]=t1[i]*k%P;
    getExp(b,t1,len);
}

void solve(){
    for(sizew=1;sizew<=n;sizew<<=1);
    static LL t1[MAXN],t2[MAXN];
    t1[0]=1; t1[1]=6; t1[2]=1;
    getPow(t1,t1,sizew,inv_v[2]);
    for(int i=0;i<sizew;i++) t2[i]=t1[i];
    t2[0]=(t2[0]+1)%P; t2[1]=(t2[1]+1)%P;
    for(int i=0;i<sizew;i++) t2[i]=t2[i]*inv_v[2]%P;
    getPow(t2,t2,sizew,m+1);
    getInv(t1,t1,sizew);
    for(int i=0;i<sizew;i++) t1[i+sizew]=t2[i+sizew]=0;
    FFT(t1,sizew<<1,1); FFT(t2,sizew<<1,1);
    for(int i=0;i<sizew<<1;i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,sizew<<1,-1);
    for(int i=1;i<=n;i++) printf("%lld ",(t1[i]+P)%P);
}

int main(){
#ifdef DEBUG
    freopen("127.in","r",stdin);
#endif
    scanf("%d%d",&m,&n);
    int _n=n;
    if(n>m) n=m;
    init();
    solve();
    for(int i=1;i<=_n-n;i++) printf("0 ");
    return 0;
}

查看详细内容

[自选题 #146] mythological I

2018-1-1 20:322018-1-1 20:32
集训队作业自选题生成函数

传送门

神tm还有双倍经验题。。。

[自选题 #133] wxh出题

查看详细内容

[自选题 #144] 基础线段树练习

2018-1-1 20:02018-1-1 20:0
集训队作业自选题FFT生成函数

传送门

不太优美的暴力题,直接在线段树的每个节点上维护所有乘上去的一次多项式,然后最后每个节点暴力分治乘起来之后,在区间的每个点上多点求值就行了。

太懒了所以就用了他给的板子(惭愧

不过这个板子竟然不支持负数,我就因为这个WA了半天。。。

#include<bits/stdc++.h>
using namespace std;

namespace Poly{
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define il inline
#define all(a) a.begin(),a.end()
#define adm(a,b,c) {a=a+b;if(a>=c)a-=c;else if(a<0)a+=c;}
#define ll long long
#define ls (k<<1)
#define rs (k<<1|1)
    const int N=5e6+5,M=1e7+5,INF=1e9,mod=998244353;
    il ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;}
    int rev[N],oo;
    il int inv(int x){return qpow(x,mod-2,mod);}
    void fft(int*a,int n,int opt){oo+=n;
        int l=0;for(int o=1;o<n;o<<=1)l++;
        re(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
        re(i,0,n)if(i<rev[i])swap(a[i],a[rev[i]]);
        for(int i=1;i<n;i<<=1){
            int wn=qpow(3,(mod-1)/(i*2),mod);if(opt==-1)wn=inv(wn);
            for(int j=0;j<n;j+=i+i){
                int w=1;re(k,0,i){
                    int x=a[j+k],y=1ll*a[j+k+i]*w%mod;
                    a[j+k]=(x+y>=mod)?(x+y-mod):(x+y);
                    a[j+k+i]=(x-y<0)?(x-y+mod):(x-y);
                    w=1ll*w*wn%mod;
                }
            }
        }if(opt==-1){
            int iv=inv(n);
            re(i,0,n)a[i]=1ll*a[i]*iv%mod;
        }
    }
    struct poly{
        vector<int>a;
        il int siz(){return a.size()-1;}
        il void resiz(int x){a.resize(x+1);}
        il int&operator[](int x){return a[x];}
        il void mt(){
            int p=siz()+1;
            while(p&&!a[p-1])p--;
            resiz(p-1);
        }
        il void trans(int*b,int n){
            resiz(n);
            rep(i,0,n)a[i]=b[i];
            mt();
        }
    };
    int mula[N],mulb[N],mulc[N];
    il poly operator*(poly&a, poly&b){
        poly c;c.resiz(a.siz()+b.siz());
        if(a.siz()<50||b.siz()<50){
            rep(i,0,a.siz())rep(j,0,b.siz())c[i+j]=(c[i+j]+1ll*a[i]*b[j])%mod;
            return c;
        }
        int n=1;while(n<=a.siz()+b.siz())n<<=1;
        rep(i,0,n)mula[i]=mulb[i]=mulc[i]=0;
        rep(i,0,a.siz())mula[i]=a[i];
        rep(i,0,b.siz())mulb[i]=b[i];
        fft(mula,n,1);fft(mulb,n,1);
        rep(i,0,n)mulc[i]=1ll*mula[i]*mulb[i]%mod;
        fft(mulc,n,-1);
        c.trans(mulc,n);
        return c;
    }
    il poly operator+(poly&a,poly&b){
        poly c;c.resiz(max(a.siz(),b.siz()));
        rep(i,0,a.siz())c[i]=a[i];
        rep(i,0,b.siz())c[i]=(c[i]+b[i])%mod;
        c.mt();
        return c;
    }
    il poly operator-(poly a,poly b){
        poly c;c.resiz(max(a.siz(),b.siz()));
        rep(i,0,a.siz())c[i]=a[i];
        rep(i,0,b.siz())c[i]=(c[i]-b[i]+mod)%mod;
        c.mt();
        return c;
    }
    int inva[N],polya[N],invb[N];
    il void getinv(int n){
        if(n==1){inva[0]=inv(polya[0]);return;}
        getinv((n+1)>>1);
        int len=1;while(len<n+n+3)len<<=1;
        re(i,n,len)invb[i]=inva[i]=0;
        re(i,0,n)invb[i]=polya[i];
        fft(invb,len,1);fft(inva,len,1);
        re(i,0,len)inva[i]=1ll*inva[i]*((mod+2-(1ll*inva[i]*invb[i]%mod))%mod)%mod;
        fft(inva,len,-1);
        re(i,n,len)inva[i]=0;
    }
    il poly inv(poly&x){
        poly y;y.resiz(x.siz());
        rep(i,0,x.siz())polya[i]=x[i];
        getinv(x.siz()+1);
        y.trans(inva,x.siz());
        return y;
    }
    il void div(poly&a,poly&b,poly&d,poly&r){
        int n=a.siz(),m=b.siz();
        if(n<m){d.resiz(0);d[0]=0;r=a;return;}
        int len=1;while(len<n+n)len<<=1;
        poly ra=a,rb=b;reverse(all(ra.a));reverse(all(rb.a));
        rb.resiz(n-m);rb=inv(rb);
        d=ra*rb;d.resiz(n-m);reverse(all(d.a));
        r=a-(b*d);
        r.mt();
    }
    poly operator/(poly a,poly b){poly d,r;div(a,b,d,r);return d;}
    poly operator%(poly a,poly b){poly d,r;div(a,b,d,r);return r;}
    int qx[N],eres[N];
    il int bru_eval(poly a,int x){
        int res=0;
        repd(i,a.siz(),0)res=(1ll*res*x+a[i])%mod;
        return res;
    }
    poly mpoly[N];
    il void evaluation(int k,poly f,int m,int*x,int*res){
        if(f.siz()<=500||m<500){
            rep(i,0,m)res[i]=bru_eval(f,x[i]);
            return;
        }poly q0,q1,tmp;
        int mid=m>>1;
        q0=mpoly[ls];q1=mpoly[rs];
        evaluation(ls,f%q0,mid,x,res);
        evaluation(rs,f%q1,m-mid-1,x+mid+1,res+1+mid);
    }
    void eval_init(int k,int m,int*x){
        if(!m){
            mpoly[k].resiz(1);
            mpoly[k][1]=1;mpoly[k][0]=mod-x[0];
            return;
        }int mid=m>>1;
        eval_init(ls,mid,x);
        eval_init(rs,m-mid-1,x+mid+1);
        mpoly[k]=mpoly[ls]*mpoly[rs];
    }
    vector<int>evaluation(poly a,vector<int>x){
        a.mt();vector<int>ans;
        ans.resize(x.size());
        re(i,0,x.size())x[i]=(x[i]%mod+mod)%mod;
        if(!x.size())return ans;
        int m=x.size()-1;
        rep(i,0,m)qx[i]=x[i];
        eval_init(1,m,qx);
        evaluation(1,a,m,qx,eres);
        rep(i,0,m)ans[i]=eres[i];
        return ans;
    }
#undef rep
#undef re
#undef repd
#undef il
#undef all
#undef adm
#undef ll
#undef ls
#undef rs
}

#define MAXN 1100000
#define LL long long

const LL P=998244353;

int n,m,sizew;
vector< pair<LL,LL> > a[MAXN];
LL ans[MAXN];

void modify(int x,int cl,int cr,int l,int r,LL t1,LL t2){
    if(l<=cl && cr<=r){
        a[x].push_back(make_pair(t1,t2));
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) modify(x<<1,cl,mid,l,r,t1,t2);
    if(r>mid) modify(x<<1|1,mid+1,cr,l,r,t1,t2);
}

Poly::poly getmul(int x,int l,int r){
    if(l==r){
        Poly::poly res;
        res.resiz(1);
        res[0]=a[x][l].second;
        res[1]=a[x][l].first;
        return res;
    }
    int mid=(l+r)>>1;
    Poly::poly t1=getmul(x,l,mid),t2=getmul(x,mid+1,r);
    return t1*t2;
}

void gao(int x,int cl,int cr){
    if(cl<cr){
        int mid=(cl+cr)>>1;
        gao(x<<1,cl,mid);
        gao(x<<1|1,mid+1,cr);
    }
    if(a[x].empty()) return;
    Poly::poly temp=getmul(x,0,a[x].size()-1);
    static vector<int> xs,ys;
    xs.resize(cr-cl+1);
    for(int i=cl;i<=cr;i++) xs[i-cl]=i;
    ys=Poly::evaluation(temp,xs);
    for(int i=cl;i<=cr;i++) ans[i]=ans[i]*ys[i-cl]%P;
}

int main(){
#ifdef DEBUG
    freopen("144.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(sizew=1;sizew<n;sizew<<=1);
    while(m--){
        int l,r;
        LL t1,t2;
        scanf("%d%d%lld%lld",&l,&r,&t2,&t1);
        t1=(t1-t2*l)%P;
        if(t1<0) t1+=P;
        modify(1,1,sizew,l,r,t2,t1);
    }
    for(int i=1;i<=n;i++) ans[i]=1;
    gao(1,1,sizew);
    for(int i=1;i<=n;i++) printf("%lld ",(ans[i]+P)%P);
}

查看详细内容