QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#750077#6199. 数圈圈jason_sun0 0ms3888kbC++141.8kb2024-11-15 12:32:562024-11-15 12:32:57

Judging History

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

  • [2024-11-15 12:32:57]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3888kb
  • [2024-11-15 12:32:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005, mod=998244353;
void add(ll &x, ll y){
	x=(x+y)%mod;
}
int a[N], b[N];
ll f[N][N];
ll qp(ll x, ll y){
	ll ans=1;
	for(;y;y/=2,x=x*x%mod){
		if(y&1) ans=ans*x%mod;
	}
	return ans;
}
int main(){
//	freopen("story.in", "r", stdin);
//	freopen("story.out", "w", stdout);
	int c, n, y;
	scanf("%d%d%d", &c, &n, &y);
	for(int i=1; i<=n; ++i){
		scanf("%d", &a[i]);
	}
	for(int i=1; i<=n; ++i){
		b[i]=b[i-1];
		while(b[i]<n&&a[b[i]+1]>=i) b[i]++;
	}
	if(c<=5){
		f[0][0]=1;
		for(int i=1; i<=n; ++i){
			if(a[i]>=i){
				for(int j=0; j<=n; ++j){
					add(f[i][j], f[i-1][j]);
					add(f[i][j+1], f[i-1][j]*(a[i]-1-j));
					add(f[i][j+1], f[i-1][j]*y);
				}
			}else{
				for(int j=0; j<=n; ++j){
					add(f[i][j], f[i-1][j]);
					add(f[i][j+1], f[i-1][j]*(a[i]-j));
				}
			}
		}
		for(int i=0; i<=n; ++i){
			printf("%lld%c", f[n][i], " \n"[i==n]);
		}
	}else{
		f[n+1][0]=1;
		for(int i=n; i>=1; --i){
			if(a[i]>=i){
//				if(a[i]>=b[i]){
					for(int j=0; j<=n; ++j){
						add(f[i][j], f[i+1][j]);
						add(f[i][j+1], f[i+1][j]*(a[i]-1+y-j));
					}
//				}else{
//					ll t=(b[i]-a[i]+1)*qp(b[i]-i+1, mod-2)%mod;
//					for(int j=0; j<=n; ++j){
//						add(f[i][j], f[i+1][j]);
//						add(f[i][j+1], f[i+1][j]*(a[i]-j+(y-1)*t%mod));
//					}
//				}
			}else{
				for(int j=0; j<=n; ++j){
					add(f[i][j], f[i+1][j]);
					add(f[i][j+1], f[i+1][j]*(a[i]-j));
				}
			}
		}
		for(int i=0; i<=n; ++i){
			printf("%lld%c", f[1][i], " \n"[i==n]);
		}
	}
	return 0;
}
//6 3 1
//3 2 2
//
//0 0 1 : 1
//2 0 1 : 1
//3 0 1 : y
//0 2 1 : y
//3 2 1 : y^2
//
//0 0 2 : 1
//1 0 2 : y
//3 0 2 : 1
//0 1 2 : 1
//3 1 2 : y

/*
6 4 1
4 2 2 2

5 5 3 3 1

5 4 4 2 2
*/

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

1 915080344
1

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 3672kb

input:

15 0
1 1 1 3 6 8 10 11 11 12 13 13 14 15 15

output:

1

result:

wrong answer Answer contains longer sequence [length = 16], but output contains 1 elements

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 0ms
memory: 3888kb

input:

74999 1
1 2 3 3 4 4 4 4 4 4 4 4 7 8 8 9 9 9 10 13 13 14 14 16 19 20 21 22 24 25 25 26 26 29 31 32 32 35 35 36 38 39 39 40 41 43 43 44 45 45 45 46 48 49 50 50 50 51 53 54 57 59 59 60 60 62 63 63 65 66 69 71 73 76 78 78 78 79 79 79 80 81 81 81 82 82 83 83 85 87 89 91 94 94 94 94 98 99 99 100 100 101 1...

output:

1 2

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 0ms
memory: 3872kb

input:

15 0
15 15 15 13 13 13 12 10 10 9 9 6 6 4 2

output:

1

result:

wrong answer Answer contains longer sequence [length = 16], but output contains 1 elements

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Runtime Error

Test #38:

score: 0
Runtime Error

input:

74999 604849250
72634 60382 41531 20689 20667 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:


result:


Subtask #9:

score: 0
Skipped

Dependency #6:

0%