ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#169140 | #45. count | qmh20061363 | 100 | 180ms | 3488kb | C++11 | 1.3kb | 2023-02-23 10:31:50 | 2023-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