QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#61597	#3265. 组合数问题	Steven_lzx	100 ✓	4ms	3744kb	C++23	901b	2022-11-14 10:57:16	2022-11-14 10:57:18

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-11-14 10:57:18]
Judged

Verdict: 100
Time: 4ms
Memory: 3744kb

Show

[2022-11-14 10:57:16]
Submitted

answer

/*
 * Title: P3746 [六省联考 2017] 组合数问题
 * Source: 洛谷
 * URL: https://www.luogu.com.cn/problem/P3746
 * Author: Steven_lzx
 * Command: -std=c++23 -O2 -Wall -fno-ms-extensions
 * Date: 2022.11.14
 */
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int n,p,k,r;
vector<int> operator *(vector<int> a,vector<int> b)
{
    vector<int> res(k);
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            res[(i+j)%k]=(res[(i+j)%k]+1ll*a[i]*b[j])%p;
    return res;
}
int main()
{
    long long t;
    vector<int> a,ans;
    scanf("%d%d%d%d",&n,&p,&k,&r);
    a.resize(k);
    ans.resize(k);
    if(k==1)
        a[0]=2%p;
    else 
        a[0]=a[1]=1;
    ans[0]=1;
    t=1ll*n*k;
    while(t)
    {
        if(t&1)
            ans=ans*a;
        a=a*a;
        t>>=1;
    }
    printf("%d\n",ans[r]);
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 3ms

memory: 3712kb

input:

14 861021533 17 8

output:

109194683

result:

ok single line: '109194683'

Test #2:

score: 5

Accepted

time: 2ms

memory: 3656kb

input:

14 734575201 8 4

output:

136629647

result:

ok single line: '136629647'

Test #3:

score: 5

Accepted

time: 3ms

memory: 3744kb

input:

6 572660339 1 0

output:

result:

ok single line: '64'

Test #4:

score: 5

Accepted

time: 1ms

memory: 3500kb

input:

17 141616127 10 5

output:

87241654

result:

ok single line: '87241654'

Test #5:

score: 5

Accepted

time: 3ms

memory: 3588kb

input:

13 889947181 16 12

output:

100910764

result:

ok single line: '100910764'

Test #6:

score: 5

Accepted

time: 3ms

memory: 3580kb

input:

25 752392757 4 3

output:

424857239

result:

ok single line: '424857239'

Test #7:

score: 5

Accepted

time: 4ms

memory: 3532kb

input:

553999928 2 45 26

output:

result:

ok single line: '0'

Test #8:

score: 5

Accepted

time: 3ms

memory: 3660kb

input:

843993365 943947738 1 0

output:

470996456

result:

ok single line: '470996456'

Test #9:

score: 5

Accepted

time: 1ms

memory: 3744kb

input:

855636225 749698583 2 0

output:

545006096

result:

ok single line: '545006096'

Test #10:

score: 5

Accepted

time: 3ms

memory: 3496kb

input:

969348092 956297536 2 1

output:

679600512

result:

ok single line: '679600512'

Test #11:

score: 5

Accepted

time: 2ms

memory: 3500kb

input:

650 660260759 45 16

output:

173373801

result:

ok single line: '173373801'

Test #12:

score: 5

Accepted

time: 3ms

memory: 3712kb

input:

598 221558443 41 40

output:

199993457

result:

ok single line: '199993457'

Test #13:

score: 5

Accepted

time: 4ms

memory: 3612kb

input:

863 269455309 42 29

output:

172561433

result:

ok single line: '172561433'

Test #14:

score: 5

Accepted

time: 3ms

memory: 3496kb

input:

28627 269441503 34 24

output:

180377871

result:

ok single line: '180377871'

Test #15:

score: 5

Accepted

time: 3ms

memory: 3616kb

input:

36656 67854541 25 6

output:

result:

ok single line: '2429047'

Test #16:

score: 5

Accepted

time: 0ms

memory: 3500kb

input:

27459 172755593 27 20

output:

73460042

result:

ok single line: '73460042'

Test #17:

score: 5

Accepted

time: 4ms

memory: 3744kb

input:

743268139 705178739 33 19

output:

311756018

result:

ok single line: '311756018'

Test #18:

score: 5

Accepted

time: 0ms

memory: 3660kb

input:

934248626 620145553 43 16

output:

121876656

result:

ok single line: '121876656'

Test #19:

score: 5

Accepted

time: 4ms

memory: 3524kb

input:

619290070 907487131 38 19

output:

213941765

result:

ok single line: '213941765'

Test #20:

score: 5

Accepted

time: 4ms

memory: 3732kb

input:

507684930 711845893 28 24

output:

419183631

result:

ok single line: '419183631'

Extra Test:

score: 0

Extra Test Passed