F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2962 >> TLE求助。就是非常的慢。
27rabbit @ 2017-10-26 20:45:06
[ Quote ] [ Edit ] [ Delete ] 1#
为什么会TLE啊。
#include<bits/stdc++.h>
#define lca long long
using namespace std;
const int MX = 50005 ;
const lca mod = 19940417 ;
int n,m,l,r,xx;
lca x,a[MX],c[MX][22];
char op[105];
struct tree{
int l,r,ine,len;
lca h[25],add;
lca & operator [] (int x) { return h[x]; }
}tr[MX<<2];
struct node{
lca h[25];
lca & operator [](int x) { return h[x]; }
};
lca qpow(lca a,int b)
{
lca res=1,base=a;
while(b)
{
if(b&1) res=res*base%mod;
base=base*base%mod;
b>>=1;
}
return res;
}

void build(int ro,int l,int r)
{
tr[ro].l=l;tr[ro].r=r;tr[ro].len=tr[ro].r-tr[ro].l+1;
tr[ro].add=tr[ro].ine=0;
for(int i=1;i<=20;i++) tr[ro].h[i]=0;
tr[ro].h[0]=1;
if(l==r)
{
tr[ro].h[1]=(a[l]%mod+mod)%mod;
return ;
}
int mid=(l+r)>>1;
build(ro<<1,l,mid);
build(ro<<1|1,mid+1,r);
for(int i=1;i<=min(20,tr[ro].len);i++)
for(int j=0;j<=i;j++)
tr[ro].h[i]=(tr[ro].h[i]+(tr[ro<<1].h[j]*tr[ro<<1|1].h[i-j]%mod+mod)%mod)%mod;
}

void pushdown(int ro)
{
if(!tr[ro].add&&!tr[ro].ine) return ;
if(tr[ro].ine)
{
for(int i=1;i<=20;i+=2)
tr[ro<<1].h[i]=(-tr[ro<<1].h[i]+mod)%mod,tr[ro<<1|1].h[i]=(-tr[ro<<1|1].h[i]+mod)%mod;
tr[ro].ine=0;
tr[ro<<1].add=-tr[ro<<1].add;tr[ro<<1|1].add=-tr[ro<<1|1].add;
tr[ro<<1].ine^=1;tr[ro<<1|1].ine^=1;
}
if(!tr[ro].add) return ;
lca x=tr[ro].add;
for(int i=20;i;i--)
for(int j=0;j<i;j++)
tr[ro<<1].h[i]=(tr[ro<<1].h[i]+tr[ro<<1].h[j]*qpow((x%mod+mod)%mod,i-j)%mod*c[tr[ro<<1].len-j][i-j]%mod)%mod;
for(int i=20;i;i--)
for(int j=0;j<i;j++)
tr[ro<<1|1].h[i]=(tr[ro<<1|1].h[i]+tr[ro<<1|1].h[j]*qpow((x%mod+mod)%mod,i-j)%mod*c[tr[ro<<1|1].len-j][i-j]%mod)%mod;
(tr[ro<<1].add+=tr[ro].add)%=mod;(tr[ro<<1|1].add+=tr[ro].add)%=mod;
tr[ro].add=0;
}

tree ask(int ro,int l,int r)
{
if (tr[ro].l == l && tr[ro].r == r)
{
return tr[ro];
}
pushdown(ro);
int mid=(tr[ro].l+tr[ro].r)>>1;
if(r<=mid) return ask(ro<<1,l,r);
else if(l>mid) return ask(ro<<1|1,l,r);
else
{
tree L = ask(ro<<1,l,mid);
tree R = ask(ro<<1|1,mid+1,r);
tree temp ;
for(int i=1;i<=20;i++) temp[i]=0;
temp[0]=1;
for(int i=1;i<=20;i++)
for(int j=0;j<=i;j++)
temp[i]=(temp[i]+(L[j]*R[i-j]%mod+mod)%mod)%mod;
return temp;
}
}

void change(int ro,int l,int r,lca x)
{
if(tr[ro].l==l&&tr[ro].r==r)
{
for(int i=20;i;i--)
for(int j=0;j<i;j++)
tr[ro].h[i]=(tr[ro].h[i]+tr[ro].h[j]*qpow((x%mod+mod)%mod,i-j)%mod*c[tr[ro].len-j][i-j]%mod)%mod;
tr[ro].add+=x;
return ;
}
pushdown(ro);
int mid=(tr[ro].l+tr[ro].r)>>1;
if(r<=mid) change(ro<<1,l,r,x);
else if(l>mid) change(ro<<1|1,l,r,x);
else change(ro<<1,l,mid,x),change(ro<<1|1,mid+1,r,x);
for(int i=1;i<=20;i++) tr[ro].h[i]=0;
tr[ro].h[0]=1;
for(int i=1;i<=min(20,tr[ro].len);i++)
for(int j=0;j<=i;j++)
tr[ro].h[i]=(tr[ro].h[i]+(tr[ro<<1].h[j]*tr[ro<<1|1].h[i-j]%mod+mod)%mod)%mod;
}

void inver(int ro,int l,int r)
{
if(tr[ro].l==l&&tr[ro].r==r)
{
for(int i=1;i<=20;i++)
if(i&1) tr[ro].h[i]=(-tr[ro].h[i]+mod)%mod;
tr[ro].add=-tr[ro].add;
tr[ro].ine^=1;
return ;
}
pushdown(ro);
int mid=(tr[ro].l+tr[ro].r)>>1;
if(r<=mid) inver(ro<<1,l,r);
else if(l>mid) inver(ro<<1|1,l,r);
else inver(ro<<1,l,mid),inver(ro<<1|1,mid+1,r);
for(int i=1;i<=20;i++) tr[ro].h[i]=0;
tr[ro].h[0]=1;
for(int i=1;i<=min(20,tr[ro].len);i++)
for(int j=0;j<=i;j++)
tr[ro].h[i]=(tr[ro].h[i]+(tr[ro<<1].h[j]*tr[ro<<1|1].h[i-j]%mod+mod)%mod)%mod;
}

int rd()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') f=c=='-'?-1:1,c=getchar();
while(c>='0'&&c<='9') x=10*x+c-'0',c=getchar();
return x*f;
}

int main()
{
freopen("a.in","r",stdin);
freopen("wa.out","w",stdout);
n=rd(),m=rd();
for(int i=0;i<=n+1;i++) c[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=min(i,20);j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
for(int i=1;i<=n;i++) a[i]=rd();
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%s",op);
if(op[0]=='I')
{
scanf("%d%d%lld",&l,&r,&x);
change(1,l,r,x);
}
else if(op[0]=='Q')
{
scanf("%d%d%d",&l,&r,&xx);
tree tmp = ask(1, l, r);
printf("%lld\n", tmp[xx]);
}
else
{
scanf("%d%d",&l,&r);
inver(1,l,r);
}
}
}

/*

5 5

1 2 3 4 5

I 2 3 1

Q 2 4 2

R 1 5

I 1 3 -1

Q 1 5 1


*/
27rabbit @ 2017-10-27 08:51:15
[ Quote ] [ Edit ] [ Delete ] 2#
好吧 已经A了。 我就不应该用快速幂。
[Top] [Previous Page] [Next Page]

HOME Back