NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #199965 | #177. move | snow_trace | 100 | 4145ms | 46516kb | C++11 | 925b | 2023-12-24 11:40:08 | 2023-12-24 12:19:06 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000000007;
int inv[2400005],jie[2400005];
int INV[2000005];
int qp(int p,int q){
int ans = 1,pro = p;
while(q){
if(q&1)ans = ans*pro%mod;
pro = pro*pro%mod;q>>=1;
}return ans;
}int C(int n,int m){
return jie[n]*inv[m]%mod*inv[n-m]%mod;
}int Cat(int n){
//喵喵喵。
return C(2*n,n)*INV[n+1]%mod;
}void solve(){
int ans =0 ,n;cin >> n;
for(int i = 0;i<=n/2;i++){
// cout << C(n,2*i) << " " << Cat(i) << endl;
ans = ans+(C(n,2*i)*Cat(i))%mod;ans%=mod;
}cout << ans << endl;
}
signed main(){
jie[0] = 1;inv[0] = 1;
for(int i = 1;i<=2400000;i++)jie[i] = jie[i-1]*i%mod;
INV[0] = 0;for(int i = 1;i<=1000005;i++)INV[i] = qp(i,mod-2);
inv[2400000] = qp(jie[2400000],mod-2);
for(int i = 2400000-1;i>=1;i--)inv[i] = inv[i+1]*(i+1)%mod;
int t;cin >> t;
while(t--){
solve();
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 176ms
memory: 46516kb
input:
10 87 126 336 401 396 393 990 967 308 130
output:
952886086 778103891 301307310 497097012 267466056 695715027 490133361 19295392 313508734 87611670
result:
ok 10 lines
Test #2:
score: 5
Accepted
time: 186ms
memory: 46516kb
input:
10 776 458 70 270 555 836 935 748 272 375
output:
692921871 445495094 774348257 379818824 888898709 174497833 196545526 118997364 299113390 299856448
result:
ok 10 lines
Test #3:
score: 5
Accepted
time: 185ms
memory: 46512kb
input:
10 855 340 58 805 522 354 251 543 823 269
output:
615565992 819883319 298217690 69689203 884819632 264378106 122305893 483673609 538195482 765591101
result:
ok 10 lines
Test #4:
score: 5
Accepted
time: 183ms
memory: 46512kb
input:
10 861 814 845 431 88 290 723 925 653 987
output:
66379951 218730106 646412481 779603910 934817196 549036495 938207208 515670413 187358499 885002046
result:
ok 10 lines
Test #5:
score: 5
Accepted
time: 187ms
memory: 46512kb
input:
10 5139 6360 6177 3920 1126 9257 5310 927 1028 723
output:
53992314 779209990 272656703 726194903 575528693 99668723 175131710 16492713 58158406 938207208
result:
ok 10 lines
Test #6:
score: 5
Accepted
time: 183ms
memory: 46512kb
input:
10 421 6323 1406 4271 9545 241 9785 6155 8416 8625
output:
504938765 241955822 418503361 879313548 600795516 401159863 845118197 688275255 813359771 170747506
result:
ok 10 lines
Test #7:
score: 5
Accepted
time: 197ms
memory: 46516kb
input:
10 1623 7654 2419 5220 7788 6086 4514 878 8719 889
output:
985056431 366520371 610623700 79873919 152612466 564409096 826125318 108992217 884889426 299052566
result:
ok 10 lines
Test #8:
score: 5
Accepted
time: 183ms
memory: 46516kb
input:
10 4834 9049 5788 5053 2368 678 7019 8699 6095 9771
output:
894248955 48762405 157733240 975780451 870697369 618636072 8225406 846511000 723654845 466048177
result:
ok 10 lines
Test #9:
score: 5
Accepted
time: 190ms
memory: 46516kb
input:
10 9992 9411 7282 2934 2901 2668 6567 4524 4102 8524
output:
75603159 139639091 827313831 749841764 833868754 310259549 804778809 416380457 20118359 546399661
result:
ok 10 lines
Test #10:
score: 5
Accepted
time: 184ms
memory: 46516kb
input:
10 9520 2862 3208 7053 9602 2486 9472 8500 3375 6827
output:
168898108 549139767 780176643 823630021 91024868 918528824 298818369 236242005 173037285 224016415
result:
ok 10 lines
Test #11:
score: 5
Accepted
time: 244ms
memory: 46516kb
input:
10 59737 856616 467799 850140 940542 645886 381456 829699 317966 558490
output:
839529689 148943889 832435699 656537703 309790708 896597601 884248120 847282933 610220680 17852453
result:
ok 10 lines
Test #12:
score: 5
Accepted
time: 210ms
memory: 46516kb
input:
10 836166 344091 589267 224275 743829 124824 37191 619801 314432 25360
output:
363572876 802728099 713874676 652189567 833071556 653110228 600371759 443480105 341963835 459920462
result:
ok 10 lines
Test #13:
score: 5
Accepted
time: 206ms
memory: 46512kb
input:
10 619868 45579 115131 121441 523910 321297 324365 602432 805322 490275
output:
528209934 480081255 386752639 15197841 617475320 8989877 616139785 763612257 554465540 480653058
result:
ok 10 lines
Test #14:
score: 5
Accepted
time: 226ms
memory: 46516kb
input:
10 552883 123886 867678 885767 850366 997032 984348 337236 233611 175426
output:
910799573 555873268 275513814 647312715 798769572 133859592 837931577 653969046 453890146 433794677
result:
ok 10 lines
Test #15:
score: 5
Accepted
time: 230ms
memory: 46516kb
input:
10 395505 432537 433480 262843 655874 343802 741245 868350 317808 682914
output:
781690159 128762586 44286220 902962745 242841990 280305487 885695030 246608547 143918021 262112863
result:
ok 10 lines
Test #16:
score: 5
Accepted
time: 238ms
memory: 46516kb
input:
10 63349 886119 176835 613938 308562 578253 594380 699798 689504 617810
output:
583981305 176628003 564919936 576538515 775560152 143079589 563319325 834895660 585267643 507384150
result:
ok 10 lines
Test #17:
score: 5
Accepted
time: 236ms
memory: 46512kb
input:
10 346593 166648 733852 27658 749332 551494 306467 928849 204793 778283
output:
772457634 24388769 933904578 513219933 329059863 109045106 455847970 560314790 989158553 189795809
result:
ok 10 lines
Test #18:
score: 5
Accepted
time: 252ms
memory: 46512kb
input:
10 756444 771536 854707 86019 86784 666644 755548 534218 82420 950867
output:
371708117 254410932 897168639 296496017 532423155 174791785 399453127 566608229 764210643 276037323
result:
ok 10 lines
Test #19:
score: 5
Accepted
time: 236ms
memory: 46512kb
input:
10 803327 236316 216530 558863 957651 635525 773678 28658 600968 485504
output:
783030543 907156811 592914588 488077290 398405119 265899907 552853838 178755889 861447556 422291694
result:
ok 10 lines
Test #20:
score: 5
Accepted
time: 213ms
memory: 46512kb
input:
10 836166 344091 589267 224275 743829 124824 37191 619801 314432 25360
output:
363572876 802728099 713874676 652189567 833071556 653110228 600371759 443480105 341963835 459920462
result:
ok 10 lines
