UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#169140#45. countqmh20061363100180ms3488kbC++111.3kb2023-02-23 10:31:502023-02-23 10:31:50

answer

#include<bits/stdc++.h>
using namespace std;
#define open(x) freopen(x ".in", "r", stdin);freopen(x ".out", "w", stdout);
#define int long long
inline int read(){int f=1;int x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-f;}c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;}
inline void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9){wr(x/10);}putchar(x%10+'0');}

int n;
const int p = 1e9 + 7;
int v[1000050];
int l , r;
int f[1000050];
int inv[100050];

inline int fpow(int a,int b){
	int R = 1;
	while(b){
		if(b & 1LL) R = R * a % p;
		a = a * a % p;
		b >>= 1LL;
	}
	return R;
}

inline int C(int n,int m){
	if(n < m){
		return 0;
	}
	return f[n] * inv[m] % p * inv[n - m] % p;
}

inline void init(){
	f[0] = f[1] = 1;
	for(int i = 1 ;i <= n + 1 ;++i){
		f[i] = f[i - 1] * i % p;
	} 
	inv[0] = 1;
	inv[n + 1]  = fpow(f[n + 1] , p - 2) % p;
	for(int  i = n ; i >= 1; --i){
		inv[i] = inv[i + 1] * (i + 1) % p;
	} 
	return;
}

signed main(){
	n = read();
	init();
	for(int i = 1 ; i <= n + 1 ; ++i){
		int a = read();
		if(v[a]) l = v[a] , r = i;
		else v[a] = i;
	} 
	for(int i = 1 ;  i <= n + 1 ; ++i){
		int ans = (C(n+1 , i) - C(n + l - r , i - 1) + p) % p;
		wr(ans);
		printf("\n");
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

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

input:

20
7 20 14 11 9 4 8 10 5 18 17 16 3 20 1 2 6 15 12 13 19

output:

20
202
1302
5929
20279
54208
116252
203482
293929
352716
352716
293930
203490
116280
54264
20349
598...

result:

ok 21 lines

Test #2:

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

input:

20
14 4 12 11 9 3 17 5 3 16 19 13 10 20 6 15 7 1 8 2 18

output:

20
193
1194
5305
17969
48076
103904
184042
269620
328406
333268
281554
197302
113900
53584
20213
596...

result:

ok 21 lines

Test #3:

score: 10
Accepted
time: 2ms
memory: 1192kb

input:

2000
1294 742 1731 1519 930 367 338 273 108 409 707 1950 1590 1871 1117 1951 669 908 1045 134 21 487...

output:

2000
1999920
332750333
790459685
958991969
264802000
270629993
897326275
42909851
278856249
48496334...

result:

ok 2001 lines

Test #4:

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

input:

2000
41 954 1458 1904 1825 65 807 129 740 321 1885 1557 483 1417 403 1430 1671 1515 978 1891 54 1407...

output:

2000
1999074
331479218
810941152
773880129
856118938
120454879
648184077
245030489
998301454
4112180...

result:

ok 2001 lines

Test #5:

score: 10
Accepted
time: 21ms
memory: 2708kb

input:

66666
21870 42200 56079 48215 41217 49628 59822 58510 66234 42372 46220 59394 25720 57961 62595 6214...

output:

66666
222144432
12148172
819451646
217465705
647667261
649552838
950353453
166527040
284386819
44375...

result:

ok 66667 lines

Test #6:

score: 10
Accepted
time: 22ms
memory: 3236kb

input:

88888
88148 18942 84891 19402 87205 88057 13900 67137 54464 69870 80616 41743 59159 87826 82938 8326...

output:

88888
950493808
864068094
398224074
305179829
380102529
645958904
913412403
631389985
435981360
4262...

result:

ok 88889 lines

Test #7:

score: 10
Accepted
time: 34ms
memory: 3488kb

input:

100000
21598 83528 89564 14089 71936 70423 29936 70398 87736 94479 66276 86957 92178 60856 95916 953...

output:

100000
999957425
383056035
5734149
558799148
962907902
634494463
854144498
32939454
970939524
238681...

result:

ok 100001 lines

Test #8:

score: 10
Accepted
time: 36ms
memory: 3488kb

input:

100000
81991 95582 83437 98910 82988 84492 65839 50008 59398 35628 15692 84369 84965 84377 88725 998...

output:

100000
999969040
390529513
412958048
745090366
586892020
17347419
533176012
611103938
4740642
615324...

result:

ok 100001 lines

Test #9:

score: 10
Accepted
time: 34ms
memory: 3484kb

input:

100000
33252 81673 46995 81395 73780 83564 81562 58936 75607 56576 89114 97596 86401 16509 92639 740...

output:

100000
999971930
620245498
963588918
356072337
842156860
376957786
41808085
379775758
620812458
4371...

result:

ok 100001 lines

Test #10:

score: 10
Accepted
time: 31ms
memory: 3488kb

input:

100000
96573 90268 46630 76853 59175 99080 53228 75349 35623 28726 89433 76400 91367 88446 87353 855...

output:

100000
999963192
900142556
503084231
94364756
676240612
551658024
546207816
621326638
432743964
3675...

result:

ok 100001 lines

Extra Test:

score: 0
Extra Test Passed