QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116464#6513. Expression 3wangyian2022TL 1ms3444kbC++142.0kb2023-06-29 11:08:492023-06-29 11:08:50

Judging History

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

  • [2024-02-14 13:23:19]
  • hack成功,自动添加数据
  • (/hack/531)
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 11:08:50]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3444kb
  • [2023-06-29 11:08:49]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
const int Q=200005;
const int INF=(1<<30);
const int mod=998244353;
typedef long long ll;
#define rg register int
#define cint const register int
//char ibuf[1<<21],*IP1=ibuf,*IP2=ibuf;
//#define gc() (__builtin_expect(IP1==IP2,0)&&(IP2=(IP1=ibuf)+fread(ibuf,1,1<<21,stdin),__builtin_expect(IP1==IP2,0))?EOF:*IP1++)
#define gc getchar
#define pc putchar
inline bool ig(const char c){return c>=48&&c<=57;}
inline void read(rg&oi){char c;rg f=1,res=0;while(c=gc(),(!ig(c))&&c^'-');c^'-'?res=(c^48):f=-1;while(c=gc(),ig(c))res=res*10+(c^48);oi=f*res;}
inline void print(rg oi){char io[23];rg l=0;if(oi<0)pc('-'),oi=~oi+1;do io[++l]=(oi%10+48);while(oi/=10);for(;l;--l)pc(io[l]);}
inline void write(cint oi,const char c){print(oi);pc(c);}char _ST_;
int prd[Q],ivp[Q];
inline int inc(cint x,cint y){return x+y<mod?x+y:x+y-mod;}
inline int dec(cint x,cint y){return x>=y?x-y:x-y+mod;}
inline int mul(cint x,cint y){return 1ll*x*y%mod;}
inline void Inc(rg&x,cint y){((x+=y)>=mod)&&(x-=mod);}
inline void Dec(rg&x,cint y){((x-=y)<0)&&(x+=mod);}
inline void Mul(rg&x,cint y){x=1ll*x*y%mod;}
inline int pow(rg x,rg y){rg res=1;for(;y;y>>=1,Mul(x,x))(y&1)&&(Mul(res,x),1);return res;}
inline int Inv(cint x){return pow(x,mod-2);}
inline int binom(cint N,cint M){return N<M||N<0||M<0?0:mul(prd[N],mul(ivp[M],ivp[N-M]));}
int n,a[Q],b[Q];
char _ED_;int main(){
	fprintf(stderr,"memory:%llu MB\n",(&_ST_-&_ED_)>>20);
	read(n);for(rg i=1;i<=n;++i)read(a[i]),a[i]%=mod;{
	char c;while(c=gc(),c^'+'&&c^'-');b[1]=(c=='-'?mod-1:1);
	for(rg i=2;i<n;++i)c=gc(),b[i]=(c=='-'?mod-1:1);}
	prd[0]=ivp[0]=1;for(rg i=1;i<=n;++i)prd[i]=mul(prd[i-1],i);
	ivp[n]=Inv(prd[n]);for(rg i=n-1;i>=1;--i)ivp[i]=mul(ivp[i+1],i+1);
	rg res=mul(prd[n-1],a[1]);
	for(rg i=1;i<n;++i){
		rg cnt=b[i];for(rg j=i-1;j>=1;--j)Mul(cnt,inc(i-j,b[j]));
		Inc(res,mul(cnt,mul(mul(prd[n-1],ivp[i]),a[i+1])));
	}
	write(res,'\n');
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3444kb

input:

4
9 1 4 1
-+-

output:

46

result:

ok 1 number(s): "46"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1860kb

input:

5
1 2 3 4 5
+-+-

output:

998244313

result:

ok 1 number(s): "998244313"

Test #3:

score: -100
Time Limit Exceeded

input:

100000
664815434 205025136 871445392 797947979 379688564 336946672 231295524 401655676 526374414 670533644 156882283 372427821 700299596 166140732 677498490 44858761 185182210 559696133 813911251 842364231 681916958 114039865 222372111 784286397 437994571 152137641 650875922 613727135 209302742 5321...

output:


result: