QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#223840 | #7438. 樋口円香 | Nahidameow | TL | 978ms | 17336kb | C++23 | 6.0kb | 2023-10-22 17:54:19 | 2023-10-22 17:54:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pd push_back
#define all(x) x.begin(),x.end()
//==============================================================
ll QP(ll x,ll y,ll mod){
ll ans=1;
for(;y;y>>=1,x=x*x%mod)
if(y&1)
ans=ans*x%mod;
return ans;
}
ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
//==============================================================1
const int BUFSIZE=1<<20;
char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
char tmp[BUFSIZE];int ct=0;
inline char getch(){
if(is==it)
it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
return is==it?EOF:*is++;
}
namespace IO{
int readInt(){
int x=0,y=0;char c=0;
while(!isdigit(c))
y|=c=='-',c=getch();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();
return !y?x:-x;
}
void flush(){
fwrite(tmp,1,ct,stdout);
ct=0;
}
void putch(char c){
tmp[ct++]=c;
if(ct==BUFSIZE)flush();
}
void putint(int x){
char q[10];
if(x==0)putch('0');
int top=0;
while(x)q[top++]=(x%10+'0'),x/=10;
while(top--)putch(q[top]);
}
}
const int N=3e5+10;
const int M=6e5+1;
const int mod=1004535809,g=3,G=inv(3,mod);
//int w[40]={0,998244352,911660635,372528824,929031873,452798380,922799308,781712469,476477967,
// 166035806,258648936,584193783,63912897,350007156,666702199,968855178,629671588,24514907,
// 996173970,363395222,565042129,733596141},
// w0[40]={0,998244352,86583718,509520358,337190230,87557064,609441965,135236158,304459705,685443576,
// 381598368,335559352,129292727,358024708,814576206,708402881,283043518,3707709,121392023,
// 704923114,950391366,428961804};
//ll g1=QP(opt==1?g:gi,(mod-1)/(i<<1),mod);
//void init1(){
// for(int i=1,p=1;i<=2e6;i<<=1,p++)w[p]=QP(g,(mod-1)/(i<<1),mod);
// for(int i=1,p=1;i<=2e6;i<<=1,p++)w0[p]=QP(gi,(mod-1)/(i<<1),mod);
//}
//vector<int> rev;
int gi[N];
//void Resize(int n){rev.resize(n<<1);}
void init1(int n){
for(int i=2;i<=n;i<<=1){
int gn=QP(G,(mod-1)/i,mod);
gi[i>>1]=1;
for(int j=(i>>1)+1;j<i;j++)
gi[j]=1ll*gi[j-1]*gn%mod;
}
}
namespace Math{
//int fac[N],nfac[N];
int Iv[N];
// void initfac(){
// fac[0]=1;for(int i=1;i<=N-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
// nfac[N-10]=inv(fac[N-10],mod);for(int i=N-11;~i;i--)nfac[i]=1ll*nfac[i+1]*(i+1)%mod;
// }int C(int x,int y){return x<0||y<0||x<y?0:1ll*fac[x]*nfac[y]%mod*nfac[x-y]%mod;}
void initinv(){
Iv[1]=1;
for(int i=2;i<=N-10;i++)
Iv[i]=1ll*(-1ll*Iv[mod%i]*(mod/i)%mod+mod)%mod;
}
}
#define add(x) (x+(x<0?mod:0)-(x>=mod?mod:0))
struct Poly{
vector<int> v;
inline void read(int n){v.resize(n+1);for(int i=0;i<=n;i++){v[i]=IO::readInt();if(v[i]>=mod)v[i]-=mod;};}
inline void write(int n){for(int i=0;i<=n;i++)printf("%d ",v[i]);puts("");return;}
inline void debug(){for(auto y:v)printf("%d ",y);puts("");return;}
//=========================================================================
inline void clear(int n){while(v.size()>n+1)v.pop_back();}
//=========================================================================
inline int operator [](const int &i)const{
if(v.size()<=i)return 0;
else return v[i];
}inline int& operator [](const int &i){
if(v.size()<=i)v.resize(i+1);
return v[i];
}
//==========================================================================
inline int init2(int n,int m){
int lim=0;
while((1<<lim)<=n+m)lim++;
// for(int i=0;i<(1<<lim);i++)rev[i]=(rev[i>>1]>>1)|((i&1)?(1<<lim-1):0);
return lim;
}
//==========================================================================
inline void NTT(Poly &f,const int &n){
for(int i=n>>1;i;i>>=1)
for(int j=0;j<n;j+=(i<<1))
for(int k=0,x,y;k<i;k++)
x=f[j|k],y=f[i|j|k],
f[j|k]=x+y-(x+y>=mod?mod:0),
f[i|j|k]=1ll*gi[i|k]*(x-y+(x-y<0?mod:0))%mod;
}
inline void INTT(Poly &f,const int &n){
for(int i=1;i<n;i<<=1)
for(int j=0;j<n;j+=(i<<1))
for(int k=0,x,y;k<i;k++)
x=f[j|k],y=1ll*gi[i|k]*f[i|j|k]%mod,
f[j|k]=x+y-(x+y>=mod?mod:0),f[i|j|k]=(x-y+(x-y<0?mod:0));
int Inv=inv(n,mod);
reverse(f.v.begin()+1,f.v.begin()+n);
for(int i=0;i<n;i++)f[i]=1ll*f[i]*Inv%mod;
}inline Poly convolution(Poly A,Poly B){
int lim=init2(A.v.size()-1,B.v.size()-1);
// A.debug();B.debug();
NTT(A,1<<lim);NTT(B,1<<lim);
// A.debug();B.debug();
for(int i=0;i<(1<<lim);i++)A[i]=1ll*A[i]*B[i]%mod;
INTT(A,(1<<lim));
// for(auto y:A.v)printf("%d ",y);puts("");
return A;
}
inline Poly operator * (const Poly &y){
Poly ans=convolution((*this),y);
ans.clear(((*this).v.size()-1)+(y.v.size()-1));
return ans;
}
};
const int K=1e6+10;
int n,m;
int pos[N],Pl[N],Pr[N];
int PSl[N],PSr[N];
int B;
int A[N];
int C[N];
struct Query{int l,posl,posr,L;}Q[K];
int cnt=0;
void change(int l,int r,int F){
if(pos[l]==pos[r]){
for(int i=l;i<=r;i++)
C[F-l+i]+=A[i];
return;
}
for(int i=l;i<=Pr[l];i++)C[F-l+i]+=A[i];
for(int i=Pl[r];i<=r;i++)C[F-l+i]+=A[i];
Q[++cnt]={l,pos[l]+1,pos[r]-1,F};
}
void solve(int l,int r){
int p=pos[l],len=r-l+1;
Poly A1,A2;
for(int i=1;i<=cnt;i++){
if(Q[i].posl<=p&&p<=Q[i].posr)
A1[Q[i].L+l-Q[i].l]++;
else if(p>Q[i].posr)continue;
}
for(int i=0;i<len;i++)
A2[i]=A[l+i];
A1=A1*A2;
for(int i=1;i<=n;i++)
C[i]+=A1[i];
}
int main(){
//freopen("1.in","r",stdin);
//freopen(".out","w",stdout);
Math::initinv();
init1(N-1);
n=IO::readInt();
for(int i=1;i<=n;i++)A[i]=IO::readInt();
//B=max(int(sqrt((1ll*n*n*log(n)+1ll*n*m)/m)),1);
B=2000;
for(int i=1;i<=n;i++)pos[i]=(i-1)/n+1;
for(int i=1;i<=n;i++)Pl[i]=(pos[i]-1)*B+1,Pr[i]=min(pos[i]*B,n);
for(int i=1;i<=pos[n];i++)PSl[i]=(i-1)*B+1,PSr[i]=min(PSr[i]*B,n);
m=IO::readInt();
while(m--){
int l=IO::readInt(),r=IO::readInt(),L=IO::readInt();//scanf("%d%d%d",&l,&r,&L);
change(l,r,L);
}
sort(Q+1,Q+cnt+1,[](auto x,auto y){return x.posr<y.posr;});
for(int i=1;i<=pos[n];i++)solve(PSl[i],PSr[i]);
for(int i=1;i<=n;i++)
IO::putint(C[i]),IO::putch('\n');
IO::flush();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 15932kb
input:
1000 629 353 463 242 579 37 341 579 751 331 971 209 993 230 150 893 723 872 154 456 443 858 815 904 643 97 471 510 695 436 306 499 371 971 494 147 702 903 795 968 731 890 594 590 356 63 313 564 718 680 525 284 848 154 36 858 367 454 723 351 580 80 102 308 680 598 185 681 706 494 725 951 248 570 793 ...
output:
9812 18329 25519 40685 50358 58477 67055 71202 84917 83471 95554 98972 114054 112482 126642 125010 144914 147671 141407 162102 164317 170828 171245 193368 183842 180062 189229 195363 201525 208055 211890 218246 222774 237496 232051 230084 240108 247492 257506 259433 262038 254605 259817 258900 25715...
result:
ok 1000 lines
Test #2:
score: 0
Accepted
time: 978ms
memory: 17336kb
input:
100000 984 353 333 932 661 754 360 57 828 818 156 676 408 992 550 847 743 689 198 782 144 163 27 320 781 316 966 842 84 797 588 39 867 498 675 598 345 159 491 1000 46 874 992 829 838 575 542 836 541 30 393 998 762 434 978 382 34 862 446 828 283 820 537 293 597 240 198 258 404 929 977 588 138 214 504...
output:
11337 20492 27617 38150 59067 68173 78360 91299 95892 109338 125673 129644 134532 153938 162487 181716 190109 202080 211662 217170 233126 223881 247707 269064 262512 271414 292008 286305 310010 326696 327857 340549 356849 355034 385112 396461 394276 401687 431908 429402 436902 456239 480823 466472 4...
result:
ok 100000 lines
Test #3:
score: -100
Time Limit Exceeded
input:
100000 770 158 194 936 605 941 814 119 685 202 611 549 697 350 322 412 751 477 433 316 489 211 428 467 47 155 318 646 342 664 801 700 466 584 494 455 350 801 315 65 323 248 952 506 429 320 798 591 272 702 475 708 457 911 421 957 642 737 75 483 938 415 371 945 792 88 400 928 125 850 140 313 121 4 784...