QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#506624#6168. 异构序列码性态问题neilliu50 21ms7952kbC++141.4kb2024-08-05 20:16:042024-08-05 20:16:04

Judging History

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

  • [2024-08-05 20:16:04]
  • 评测
  • 测评结果:50
  • 用时:21ms
  • 内存:7952kb
  • [2024-08-05 20:16:04]
  • 提交

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

result: