QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1308 | #828389 | #9774. Same Sum | zhenghanyun | dxbt | Success! | 2024-12-23 16:33:25 | 2024-12-23 16:33:27 |
详细
Extra Test:
Wrong Answer
time: 7ms
memory: 56900kb
input:
103744 1 11078 98237 74492 16193 69643 44785 82715 2857 32202 57161 78418 32219 69572 41462 46834 42132 36974 56197 26540 80289 25180 69381 95212 10227 45008 99405 23180 32407 25520 74527 75040 24913 67546 5979 34140 92335 44888 81897 36692 36523 77482 28692 17230 76596 69134 31152 32510 67204 55365...
output:
Yes
result:
wrong answer expected NO, found YES [1st token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#828389 | #9774. Same Sum | dxbt | WA | 1173ms | 63356kb | C++14 | 3.1kb | 2024-12-23 16:25:51 | 2024-12-23 16:47:50 |
answer
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define G(i,l,r) for(int i=(l),i##end=(r);i>=i##end;--i)
#define pii pair<int,int>
#define x first
#define y second
#define mp(x,y) make_pair(x,y)
#define ep emplace_back
using namespace std;
typedef long long ll;
constexpr int mod=998244353;
struct node
{
ll a,b,c,d,e,f,s,t;
node(){a=b=c=d=e=0,f=1;}
node(ll a1,ll b1,ll c1,ll d1,ll e1,ll f1,ll s1,ll t1)
{
s=s1,t=t1,a=a1,b=b1,c=c1,d=d1,e=e1,f=f1;
}
void add(ll x)
{
x%=mod;
ll p1=x,p2=x*p1%mod,p3=p2*p1%mod,p4=p3*p1%mod,p5=p4*p1%mod,p6=p5*p1%mod,p7=p6*p1%mod;
s=(s+7*t%mod*p1+21*a%mod*p2+35*b%mod*p3+35*c%mod*p4+21*d%mod*p5+7*e%mod*p6%mod+f*p7)%mod;
t=(t+6*a%mod*p1+15*b%mod*p2+20*c%mod*p3+15*d%mod*p4+6*e%mod*p5+f*p6%mod)%mod;
a=(a+5*b%mod*p1+10*c%mod*p2+10*d%mod*p3+5*e%mod*p4+f*p5)%mod;
b=(b+4*c%mod*p1%mod+6*d%mod*p2+4*e%mod*p3+f*p4)%mod;
c=(c+3*d%mod*p1%mod+3*e%mod*p2+f*p3)%mod;
d=(d+2*e%mod*p1+f*p2)%mod;
e=(e+f*p1)%mod;
}
node operator+(const node &A)const
{
return node{a+A.a,b+A.b,c+A.c,d+A.d,e+A.e,f+A.f,s+A.s,t+A.t};
}
void print()
{
cerr<<s<<' '<<t<<' '<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<'\n';
}
}tr[200009<<2];
ll tag[200009<<2];
ll a[200009<<2];
ll qpow(ll x,ll y)
{
ll res=1;
for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;
return res;
}
void pushdown(int o)
{
if(tag[o])
{
tag[o<<1]+=tag[o];
tag[o<<1|1]+=tag[o];
tr[o<<1].add(tag[o]);
tr[o<<1|1].add(tag[o]);
tag[o]=0;
return ;
}
}
void add(int l,int r,int o,int a,int b,int c)
{
if(a<=l && r<=b)return tr[o].add(c),tag[o]+=c,void();
int mid=l+r>>1;
pushdown(o);
if(a<=mid)add(l,mid,o<<1,a,b,c);
if(b>mid) add(mid+1,r,o<<1|1,a,b,c);
tr[o]=tr[o<<1]+tr[o<<1|1];
}
ll ask(int l,int r,int o,int a,int b)
{
if(a<=l && r<=b)return tr[o].e;
int mid=l+r>>1;
pushdown(o);
if(b<=mid)return ask(l,mid,o<<1,a,b);
if(a>mid) return ask(mid+1,r,o<<1|1,a,b);
return (ask(l,mid,o<<1,a,b)+ask(mid+1,r,o<<1|1,a,b))%mod;
}
node ask1(int l,int r,int o,int a,int b)
{
if(a<=l && r<=b)return tr[o];
int mid=l+r>>1;
pushdown(o);
if(b<=mid)return ask1(l,mid,o<<1,a,b);
if(a>mid) return ask1(mid+1,r,o<<1|1,a,b);
return (ask1(l,mid,o<<1,a,b)+ask1(mid+1,r,o<<1|1,a,b));
}
void build(int l,int r,int o)
{
if(l==r)return tr[o].add(a[l]),void();
int mid=l+r>>1;
build(l,mid,o<<1);
build(mid+1,r,o<<1|1);
tr[o]=tr[o<<1]+tr[o<<1|1];
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
int n,q;
cin>>n>>q;
F(i,1,n)cin>>a[i];
build(1,n,1);
/*node s;
s.print();
s.add(1);
s.print();
s.add(1);
s.print();*/
int test=0;
F(cc,1,q)
{
int op;
cin>>op;
if(op==1)
{
int l,r,c;
cin>>l>>r>>c;
add(1,n,1,l,r,c);
}
else
{
test++;
int l,r;
cin>>l>>r;
ll sum=ask(1,n,1,l,r)*qpow(r-l+1,mod-2)%mod;
// cerr<<"sum"<<sum<<'\n';
add(1,n,1,l,r,mod-sum);
node p=ask1(1,n,1,l,r);
// if(test==953)
// p.print();
if(p.s%mod==0&&p.c%mod==0&&p.a%mod==0)puts("Yes");
else puts("No");
add(1,n,1,l,r,sum);
}
}
return 0;
}