[自选题 #144] 基础线段树练习
2018-1-2 1:02018-1-2 1:0
不太优美的暴力题,直接在线段树的每个节点上维护所有乘上去的一次多项式,然后最后每个节点暴力分治乘起来之后,在区间的每个点上多点求值就行了。
太懒了所以就用了他给的板子(惭愧
不过这个板子竟然不支持负数,我就因为这个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);
}