QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#223866#7438. 樋口円香NahidameowRE 0ms0kbC++236.0kb2023-10-22 18:31:542023-10-22 18:31:55

Judging History

你现在查看的是最新测评结果

  • [2023-10-22 18:31:55]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-22 18:31:54]
  • 提交

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();
	//sqrt(1.0*T*T*log2(T)/Q+Q)*2
	B=sqrt(1.0*1e5*1e5*log2(1e5)/m+m)*2;
//	B=50000;
	for(int i=1;i<=n;i++)pos[i]=(i-1)/B+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(PSl[i]+B-1,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: 0
Runtime Error

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:


result: