QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#59295#838. Horrible CyclesCrysflyAC ✓78ms3664kbC++172.4kb2022-10-29 09:46:012022-10-29 09:46:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-29 09:46:03]
  • 评测
  • 测评结果:AC
  • 用时:78ms
  • 内存:3664kb
  • [2022-10-29 09:46:01]
  • 提交

answer

// what is matter? never mind. 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}
// modint
#define mod 998244353
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 5015
#define inf 0x3f3f3f3f

int n,a[maxn]; 
modint res,f[maxn];

signed main()
{
	n=read();
	For(i,1,n)a[i]=read();
	sort(a+1,a+n+1);
	f[0]=1;
	int now=0;
	For(i,1,n){
		while(now<a[i]){
			++now;
			Rep(j,n,1)f[j]+=f[j-1];
		}
		res+=f[1];
		For(j,0,n)f[j]+=f[j+1]*j*(j+1); 
	}
	For(i,1,n)res-=a[i];
	res/=2;
	cout<<res.x;
	return 0;
}

詳細信息

Test #1:

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

input:

1
1

output:

0

result:

ok answer is '0'

Test #2:

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

input:

2
2 2

output:

1

result:

ok answer is '1'

Test #3:

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

input:

3
3 3 2

output:

7

result:

ok answer is '7'

Test #4:

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

input:

10
6 6 7 7 8 8 9 9 10 10

output:

410150080

result:

ok answer is '410150080'

Test #5:

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

input:

25
19 5 16 16 19 22 13 15 19 25 1 24 7 2 4 24 3 19 1 5 5 6 19 8 18

output:

181693199

result:

ok answer is '181693199'

Test #6:

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

input:

25
25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25

output:

833207138

result:

ok answer is '833207138'

Test #7:

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

input:

50
31 15 36 25 26 32 26 22 50 49 41 36 49 35 39 18 2 3 23 18 33 15 1 45 4 47 36 34 23 3 49 16 29 48 27 25 33 15 40 3 50 50 40 14 49 36 31 6 22 1

output:

779170262

result:

ok answer is '779170262'

Test #8:

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

input:

50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50

output:

688904780

result:

ok answer is '688904780'

Test #9:

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

input:

250
138 96 246 191 156 238 201 242 233 23 236 77 26 206 203 116 18 160 164 248 249 10 220 228 125 210 172 128 127 152 209 6 79 25 164 177 87 40 57 113 203 155 57 203 99 45 221 240 244 32 238 122 138 86 237 149 19 175 215 94 212 121 245 199 234 8 46 218 204 138 206 48 162 94 238 184 120 159 57 228 14...

output:

49866440

result:

ok answer is '49866440'

Test #10:

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

input:

250
250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 ...

output:

658185020

result:

ok answer is '658185020'

Test #11:

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

input:

500
289 21 238 284 123 225 289 119 177 391 336 381 77 104 450 132 478 38 397 144 17 466 244 65 287 402 434 198 140 353 77 391 253 154 248 16 103 296 453 433 334 185 459 404 348 363 414 478 495 454 218 325 466 180 404 119 57 36 17 378 424 374 148 434 141 61 100 239 406 461 76 3 459 481 242 200 50 467...

output:

126505365

result:

ok answer is '126505365'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

500
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 ...

output:

675760977

result:

ok answer is '675760977'

Test #13:

score: 0
Accepted
time: 5ms
memory: 3460kb

input:

1000
894 197 325 232 902 183 41 481 495 266 152 704 790 458 546 258 30 366 747 546 332 816 523 683 771 152 647 967 785 793 62 915 864 667 972 536 678 183 290 164 533 374 932 943 508 627 226 823 644 596 767 620 563 613 53 340 813 164 591 752 990 342 326 157 97 25 197 373 732 224 693 539 826 835 642 9...

output:

846396949

result:

ok answer is '846396949'

Test #14:

score: 0
Accepted
time: 5ms
memory: 3408kb

input:

1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...

output:

719983487

result:

ok answer is '719983487'

Test #15:

score: 0
Accepted
time: 10ms
memory: 3592kb

input:

1500
1411 757 1313 912 262 1187 981 1462 907 180 1271 1463 269 957 28 355 805 260 975 876 1029 1170 1019 672 337 54 835 1453 1037 1116 326 578 730 311 1089 1081 849 575 1143 948 814 599 304 1206 26 788 334 1109 361 176 614 866 77 993 441 886 814 824 125 89 1256 926 727 413 412 846 1112 1251 298 1472...

output:

557496101

result:

ok answer is '557496101'

Test #16:

score: 0
Accepted
time: 9ms
memory: 3412kb

input:

1500
1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 ...

output:

275972573

result:

ok answer is '275972573'

Test #17:

score: 0
Accepted
time: 11ms
memory: 3472kb

input:

2000
271 1415 1493 921 895 953 585 322 909 77 1116 1803 892 964 1756 1407 1374 659 933 1341 1597 1828 1547 906 1573 133 1556 1421 104 1287 75 322 233 464 1519 1064 817 730 657 1075 126 1570 426 1434 1583 1785 1554 1978 1785 1126 906 1585 613 275 1475 1572 1167 764 581 505 1977 1539 281 1534 1766 185...

output:

101405198

result:

ok answer is '101405198'

Test #18:

score: 0
Accepted
time: 11ms
memory: 3464kb

input:

2000
2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 ...

output:

404199111

result:

ok answer is '404199111'

Test #19:

score: 0
Accepted
time: 26ms
memory: 3596kb

input:

3000
2457 2825 1854 314 2080 2212 320 163 220 888 1273 310 401 1661 1965 2955 717 2464 1527 329 565 2544 1083 538 79 305 274 2068 830 76 793 433 2602 2861 2873 1399 2149 1380 2217 2986 422 1661 1624 2117 1954 1136 2075 133 414 2145 1853 1062 854 2129 2090 2995 1930 2659 2379 2258 2259 2328 1749 1910...

output:

573272276

result:

ok answer is '573272276'

Test #20:

score: 0
Accepted
time: 26ms
memory: 3508kb

input:

3000
3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 ...

output:

354414340

result:

ok answer is '354414340'

Test #21:

score: 0
Accepted
time: 50ms
memory: 3508kb

input:

4000
2643 2747 3318 1706 3072 1279 1863 2197 3530 3891 2533 2305 2502 1463 1471 1911 3869 1757 2713 3828 2126 1260 106 3657 585 3774 991 2522 853 1570 2614 32 970 1851 420 2631 2584 1630 1584 3600 2015 1752 821 1904 2133 998 2596 2992 3555 3164 288 1323 1800 1791 3808 1714 3284 42 880 1419 2734 333 ...

output:

787769330

result:

ok answer is '787769330'

Test #22:

score: 0
Accepted
time: 52ms
memory: 3484kb

input:

4000
4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 ...

output:

282890964

result:

ok answer is '282890964'

Test #23:

score: 0
Accepted
time: 78ms
memory: 3528kb

input:

5000
2829 1670 679 1395 65 1242 1599 3742 4840 3702 1201 812 603 3457 1385 2163 3509 1562 603 2624 2390 2464 4938 4289 3091 3754 2900 4169 1387 2359 3628 1143 4339 2544 4775 863 1915 4473 3847 2807 4311 3652 4611 99 504 4157 4925 4851 2696 2399 2234 2096 2553 3645 3934 2946 1047 642 1678 172 2721 48...

output:

635598407

result:

ok answer is '635598407'

Test #24:

score: 0
Accepted
time: 72ms
memory: 3624kb

input:

5000
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...

output:

74560349

result:

ok answer is '74560349'

Test #25:

score: 0
Accepted
time: 78ms
memory: 3512kb

input:

5000
1 2 3 3 5 6 7 6 6 2 7 8 8 7 10 3 15 8 19 4 1 14 8 17 16 24 18 25 28 29 4 15 8 22 30 23 31 15 32 7 8 8 36 15 34 43 16 3 40 49 3 52 38 39 44 42 31 44 59 52 41 40 57 38 41 38 46 43 16 26 61 49 33 57 38 63 28 76 32 18 58 63 43 40 85 39 48 43 88 71 41 68 88 53 43 62 57 77 60 51 24 20 61 58 33 41 23 ...

output:

414429770

result:

ok answer is '414429770'