QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#506624 | #6168. 异构序列码性态问题 | neilliu | 50 | 21ms | 7952kb | C++14 | 1.4kb | 2024-08-05 20:16:04 | 2024-08-05 20:16:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
long long ksm(long long a,long long b,long long p){
long long ans = 1;
for(; b; b >>= 1){
if(b & 1) ans = ans * a % p;
a = a * a % p;
}
return ans;
}
long long fac[10000005],infac[10000005],Ca[5000005];
void init(long long n,long long p){
fac[0] = infac[0] = fac[1] = infac[1] = 1;
for(int i = 2; i <= n; i++) fac[i] = fac[i-1] * i % p;
for(int i = 2; i <= n; i++) infac[i] = infac[i-1] * ksm(i,p-2,p) % p;
}
long long C(int x,int y,long long p){
return fac[x] * infac[y] % p * infac[x-y] % p;
}
void Catalan(int n,long long p){
Ca[0] = Ca[1] = 1;
for(int i = 2; i <= n; i++) Ca[i] = Ca[i-1] * (4 * i - 2) % p * ksm((i+1),p-2,p) % p;
}
int main()
{
long long n,p;
while(cin >> n >> p){
if(n <= 3){
printf("0\n");
continue;
}
init(2*n,p);
Catalan(n,p);
long long ans = 0;
n = n-1;
for(int i = 0; i <= n; i++){
long long sum = 1;
sum = sum * ksm(2,i,p) % p;
sum = sum * C(n+i,n-i,p) % p;
sum = sum * (i == 0 ? 1 : Ca[i] + p) % p;
if((n-i) % 2 == 1) sum = sum * (-1);
ans = (ans + sum + p) % p;
}
printf("%lld\n",(fac[n+1] - 2 * ans + 2 * p) % p);
}
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 15ms
memory: 7948kb
input:
1329 281979259 3946 347158051 3102 613279651 4193 175275013 494 674092373 549 240448331 3924 588857561 1719 782159639 1781 270936499 672 589936439
output:
9022243 90375289 181500274 69392605 94572085 183988942 242547795 400947287 129450662 237048756
result:
ok 10 numbers
Test #2:
score: 10
Accepted
time: 19ms
memory: 7952kb
input:
2013 239960621 2839 377547413 4864 996482101 3196 204395311 1568 653611141 753 104807119 3006 755688737 3047 697114861 2943 384316589 2413 512454407
output:
127514501 170181578 992038090 73815433 61816960 45154402 745032291 462320547 174525842 366107086
result:
ok 10 numbers
Test #3:
score: 10
Accepted
time: 15ms
memory: 7884kb
input:
4542 497374921 4375 144420547 3310 175379389 1159 776452463 642 401409289 1214 754051891 1956 962928761 3925 282058753 2664 215149997 2050 912416861
output:
234466993 4538739 59390501 366898284 163934721 171961354 863425261 138782415 83003435 201847067
result:
ok 10 numbers
Test #4:
score: 10
Accepted
time: 21ms
memory: 7912kb
input:
4808 349909687 4602 991037059 108 14516431 3384 974151743 1250 726146471 4891 585626857 3617 211451333 358 425997931 2891 654329051 4814 64701121
output:
334429486 723833033 167634 14788268 311835630 440281445 47163985 14567537 564093849 44526802
result:
ok 10 numbers
Test #5:
score: 10
Accepted
time: 15ms
memory: 7944kb
input:
1107 524640323 1847 933584471 3406 582135349 4007 51397727 80 570372863 4186 193850947 1773 505708747 59 753490921 4244 207441401 723 3432577
output:
28404629 25931058 291914063 14907567 428621355 83313071 83042152 573879485 8114266 2470622
result:
ok 10 numbers
Test #6:
score: 0
Time Limit Exceeded
input:
350598 149719567 5656 639718861 182032 562484129 321578 733607449 396666 977259137 289217 738297893 94787 357806747 130763 912856261 129615 332700631 439091 653900939 228198 805737671 421386 35411809
output:
17579808 155419450 560026227 468297123 243029728
result:
Test #7:
score: 0
Time Limit Exceeded
input:
71980 730430429 365591 519176123 421874 939796883 442008 891121537 196686 57507407 481211 220812971 351047 410650543 262764 313392899 434798 192402149 113530 421210637 359403 379486343 396967 813975307 193616 995122811
output:
327860411 361140274 24095392 737625805 21913793
result:
Test #8:
score: 0
Time Limit Exceeded
input:
412065 473565137 427460 278321429 481215 341626709 248825 235725317 391371 550178417 166694 541821383 3035 184388593 166130 370451243 342592 79808159 98863 640391243 416610 96090131 479715 456938333 407065 630349243 289928 807773149 486842 415008521 300760 618573047
output:
227856800 239201498 95049640 48786767
result:
Test #9:
score: 0
Time Limit Exceeded
input:
401210 376894061 112020 976190981 76624 418721741 308217 29130763 275157 939661747 35829 250363831 178538 424627327 456973 351281803 88075 992733541 281595 311233067 104622 151994753 271593 41245261 319132 947462657 186811 961154149 227249 86441119 165977 701025443 471204 999330173 296567 685415303 ...
output:
137731023 920811362 295340379 23946348 428778019 85748992 320995144
result:
Test #10:
score: 0
Time Limit Exceeded
input:
372965 157601299 239698 272457617 40399 596646311 315339 562161443 166279 292784099 224605 629707601 14534 7015139 478528 718703087 129027 957763397 44039 880925107 420271 933815867 323410 164444393 160117 572839451 344095 28487981 473223 648555881 469070 150428897 447149 993828707 214989 982422577 ...
output:
109121987 262715175 356621013 297089637 223288225 339047279 4617668