QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#142058#6513. Expression 3qzez#TL 2ms12148kbC++142.7kb2023-08-18 12:36:072023-08-18 12:36:09

Judging History

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

  • [2024-02-14 13:23:19]
  • hack成功,自动添加数据
  • (/hack/531)
  • [2023-08-18 12:36:09]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:12148kb
  • [2023-08-18 12:36:07]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=4e5+5,M=2e3+5,K=63,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,A[N];char s[N];ll frc[N],inv[N],Inv[N];
ll C(int x,int y){return frc[x]*Inv[y]%mod*Inv[x-y]%mod;}
ll mpow(ll x,int y=mod-2){ll ans=1;while(y) y&1&&(ans=ans*x%mod),y>>=1,x=x*x%mod;return ans;}
namespace Poly{const int G=3,Ig=mpow(G);
	int tr[N],k;ll C[N],D[N],f[N],g[N],H[N];
	#define Bmod(x,y) (x+y>=mod?x+y-mod:x+y)
	void Init(int n){for(k=1;k<=2*n;k<<=1);for(int i=0;i<k;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?k/2:0);}
	void NTT(ll *A,int k,int Fl){
		int i,j,h;ll key,now,pus;for(i=0;i<k;i++) tr[i]<i&&(swap(A[i],A[tr[i]]),0);
		for(i=2;i<=k;i<<=1){
			for(key=mpow(Fl?G:Ig,(mod-1)/i),j=0;j<k;j+=i){
				for(now=1,h=j;h<j+i/2;h++) pus=now*A[h+i/2]%mod,A[h+i/2]=Bmod(A[h],mod-pus),A[h]=Bmod(A[h],pus),now=now*key%mod;
			}
		}if(Fl) return;ll Iv=mpow(k);for(i=0;i<k;i++) A[i]=A[i]*Iv%mod;
	}
	void Inv(ll *A,ll *B,int n){
		if(n==1){B[0]=mpow(A[0]);return;}Inv(A,B,n+1>>1);int i;Init(n);for(i=0;i<n;i++) C[i]=A[i],D[i]=B[i];
		NTT(C,k,1);NTT(D,k,1);for(i=0;i<k;i++) C[i]=D[i]*(2+mod-C[i]*D[i]%mod)%mod;NTT(C,k,0);for(i=0;i<n;i++) B[i]=C[i];
		for(i=0;i<k;i++) C[i]=D[i]=0;
	}
	void Ln(ll *A,ll *B,int n){
		int i;Inv(A,f,n);Init(n);for(i=0;i<n;i++) g[i]=A[i+1]*(i+1)%mod;NTT(f,k,1);NTT(g,k,1);for(i=0;i<k;i++) f[i]=f[i]*g[i]%mod;NTT(f,k,0);
		B[0]=0;for(i=1;i<n;i++) B[i]=f[i-1]*mpow(i)%mod;for(i=0;i<k;i++) g[i]=f[i]=0;
	}
	void Exp(ll *A,ll *B,int n){
		if(n==1){B[0]=1;return;}Exp(A,B,n+1>>1);int i;Ln(B,H,n);for(i=0;i<n;i++) H[i]=((!i)+mod+A[i]-H[i])%mod;
		Init(n);for(i=0;i<n;i++) C[i]=B[i];NTT(H,k,1);NTT(C,k,1);
		for(i=0;i<k;i++) C[i]=C[i]*H[i]%mod;NTT(C,k,0);for(i=0;i<n;i++) B[i]=C[i];for(i=0;i<k;i++) C[i]=H[i]=0;
	}
}
int main(){
	int i,j;scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&A[i]);
	scanf("%s",s+1);
	for(frc[0]=i=1;i<=n;i++) frc[i]=frc[i-1]*i%mod;
	inv[1]=1;for(i=2;i<=n;i++) inv[i]=(mod-inv[mod%i])*(mod/i)%mod;
	for(Inv[0]=i=1;i<=n;i++) Inv[i]=Inv[i-1]*inv[i]%mod;
	ll ans=A[1]*frc[n-1]%mod;
	for(i=2;i<=n;i++){
		ll tot=(s[i-1]=='+'?1:mod-1);
		for(j=1;j<i-1;j++) tot=tot*((s[j]=='+'?1:mod-1)+i-j-1)%mod;
		// cerr<<tot*frc[i-2]%mod<<'\n';
		ans+=tot*C(n-1,n-i)%mod*frc[n-i]%mod*A[i]%mod;
	}
	printf("%lld\n",ans%mod);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12148kb

input:

4
9 1 4 1
-+-

output:

46

result:

ok 1 number(s): "46"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11936kb

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: