QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#564782#7875. Queue SortingBird#WA 77ms3976kbC++171.2kb2024-09-15 14:29:162024-09-15 14:29:18

Judging History

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

  • [2024-09-15 14:29:18]
  • 评测
  • 测评结果:WA
  • 用时:77ms
  • 内存:3976kb
  • [2024-09-15 14:29:16]
  • 提交

answer

#include<bits/stdc++.h>
#define N 500
using namespace std;
const int mod=998244353;
int n,a[N+5],f[N+5],g[N+5],ans;
inline int fmod(const int &x) {return x<mod?x:x+mod;}
inline int qmod(const int &x) {return x<0?x+mod:x;}
inline void add(int &x,const int &y) {x=fmod(x+y);}
inline void sub(int &x,const int &y) {x=qmod(x-y);}
inline int quick_pow(int x,int b)
{
	int ret=1;
	for(;b;b>>=1,x=1ll*x*x%mod)
		if(b&1) ret=1ll*ret*x%mod;
	return ret;
}
inline int inv(int x) {return quick_pow(x,mod-2);}
int fac[N+5],ifac[N+5];
void init(int n=N)
{
	fac[0]=1;for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=inv(fac[n]);for(int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m)
{
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	scanf("%d",&n),init(N);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	f[a[n]]=1;
	for(int i=n-1;i;--i) if(a[i])
	{
		memset(g,0,sizeof g);
		for(int j=0;j<=N;++j) if(f[j])
		{
			add(g[j+a[i]],f[j]);
			for(int k=1;k<=a[i];++k)
				for(int x=1;x<=j;++x)
					add(g[x+a[i]-k],1ll*f[j]*C(j-x+k-1,k-1)%mod);
		}
		swap(f,g);
	}
	for(int i=0;i<=N;++i) add(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3964kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Wrong Answer
time: 77ms
memory: 3976kb

input:

300
0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...

output:

-288856890

result:

wrong answer 1st numbers differ - expected: '507010274', found: '-288856890'