QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#630390#6410. Classical DP ProblemmayunfeiWA 0ms3972kbC++17845b2024-10-11 18:16:132024-10-11 18:16:17

Judging History

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

  • [2024-10-11 18:16:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3972kb
  • [2024-10-11 18:16:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005,p=998244353;
int n,r,m,a[maxn],b[maxn],f[maxn][maxn],v[5],jcr=1,loc;
int main()
{
	scanf("%d",&n),loc=n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	while(r<n&&a[n-r]>r) (jcr*=(++r))%=p;
	f[n-r][0]=1;
	for(int i=1;i<=a[n-r];i++) f[n-r][i]=0;
	for(int i=n-r+1;i<=n;i++)
		for(int j=0;j<=a[n-r];j++)
			f[i][j]=(1ll*(j+a[i]-a[n-r])*f[i-1][j]+(j?(a[n-r]-j+1ll)*f[i-1][j-1]:0))%p;
	v[1]=f[n][a[n-r]],m=a[n];
	for(int i=m;i>=1;i--)
	{
		if(loc>1&&a[loc-1]>=i) loc--;
		b[m-i+1]=n-loc+1;
	}
	f[m-r][0]=1;
	for(int i=1;i<=b[m-r];i++) f[m-r][i]=0;
	for(int i=m-r+1;i<=m;i++)
		for(int j=0;j<=b[m-r];j++)
			f[i][j]=(1ll*(j+b[i]-b[m-r])*f[i-1][j]+(j?(b[m-r]-j+1ll)*f[i-1][j-1]:0))%p;
	v[2]=f[m][b[m-r]];
	printf("%d %d\n",r,((v[1]+v[2]-jcr)%p+p)%p);
	return 0;
}

詳細信息

Test #1:

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

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

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

input:

1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

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

input:

2
1 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #4:

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

input:

2
2 2

output:

2 6

result:

ok 2 number(s): "2 6"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3964kb

input:

3
1 1 1

output:

1 2

result:

wrong answer 2nd numbers differ - expected: '3', found: '2'