QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133972 | #3265. 组合数问题 | NOI_AK_ME | 100 ✓ | 2ms | 3556kb | C++11 | 2.2kb | 2023-08-02 19:16:27 | 2023-08-02 19:16:28 |
Judging History
answer
# include <bits/stdc++.h>
using i64 = long long ;
using namespace std ;
namespace IO
{
template < typename T > inline T Read ()
{
T v = 0, f = 1 ; char c = getchar () ;
while ( !isdigit ( c ) )
{
if ( c == '-' ) f = -1 ;
c = getchar () ;
}
while ( isdigit ( c ) )
{
v = ( v << 3 ) + ( v << 1 ) + ( c - '0' ) ;
c = getchar () ;
}
return v *= f ;
}
template < typename T > inline void Write ( T v )
{
if ( v < 0 ) putchar ( '-' ), v = -v ;
if ( v > 9 ) Write ( v / 10 ) ;
return putchar ( v % 10 + '0' ), void () ;
}
}
using IO :: Read ;
using IO :: Write ;
namespace Program
{
const int MAXN = 55 ;
int n, p, k, r ;
int C[MAXN][MAXN] ;
vector <int> f ;
inline int Get ( int v ) { return v - ( v >= p ) * p ; }
inline void Init ()
{
C[0][0] = 1 ;
for ( register int i = 1; i <= k; ++i )
{
C[i][0] = 1 ;
for ( register int j = 1; j <= i; ++j ) C[i][j] = Get ( C[i - 1][j] + C[i - 1][j - 1] ) ;
}
f.resize ( k ), f[0] = 2 % p ;
for ( register int i = 1; i < k; ++i ) f[i] = C[k][i] ;
return ;
}
inline vector <int> Multiply ( vector <int> &a, vector <int> &b )
{
vector <int> res ; res.resize ( k ) ;
for ( register int i = 0; i < k; ++i ) for ( register int j = 0; j < k; ++j ) res[( i + j ) % k] = Get ( res[( i + j ) % k] + 1LL * a[i] * b[j] % p ) ;
return res ;
}
inline void Solve ( vector <int> &a, int b )
{
vector <int> res ( k ) ; res.resize ( k ), res[0] = 1 ;
while ( b )
{
if ( b & 1 ) res = Multiply ( res, a ) ;
a = Multiply ( a, a ), b >>= 1 ;
}
return Write ( res[r] ), putchar ( '\n' ), void () ;
}
inline int Run ()
{
n = Read <int> (), p = Read <int> (), k = Read <int> (), r = Read <int> (), Init (), Solve ( f, n ) ;
return 0 ;
}
}
int main () { return Program :: Run () ; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 1ms
memory: 3464kb
input:
14 861021533 17 8
output:
109194683
result:
ok single line: '109194683'
Test #2:
score: 5
Accepted
time: 1ms
memory: 3436kb
input:
14 734575201 8 4
output:
136629647
result:
ok single line: '136629647'
Test #3:
score: 5
Accepted
time: 1ms
memory: 3440kb
input:
6 572660339 1 0
output:
64
result:
ok single line: '64'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3552kb
input:
17 141616127 10 5
output:
87241654
result:
ok single line: '87241654'
Test #5:
score: 5
Accepted
time: 1ms
memory: 3504kb
input:
13 889947181 16 12
output:
100910764
result:
ok single line: '100910764'
Test #6:
score: 5
Accepted
time: 1ms
memory: 3500kb
input:
25 752392757 4 3
output:
424857239
result:
ok single line: '424857239'
Test #7:
score: 5
Accepted
time: 1ms
memory: 3520kb
input:
553999928 2 45 26
output:
0
result:
ok single line: '0'
Test #8:
score: 5
Accepted
time: 1ms
memory: 3480kb
input:
843993365 943947738 1 0
output:
470996456
result:
ok single line: '470996456'
Test #9:
score: 5
Accepted
time: 1ms
memory: 3472kb
input:
855636225 749698583 2 0
output:
545006096
result:
ok single line: '545006096'
Test #10:
score: 5
Accepted
time: 1ms
memory: 3444kb
input:
969348092 956297536 2 1
output:
679600512
result:
ok single line: '679600512'
Test #11:
score: 5
Accepted
time: 1ms
memory: 3504kb
input:
650 660260759 45 16
output:
173373801
result:
ok single line: '173373801'
Test #12:
score: 5
Accepted
time: 1ms
memory: 3440kb
input:
598 221558443 41 40
output:
199993457
result:
ok single line: '199993457'
Test #13:
score: 5
Accepted
time: 2ms
memory: 3508kb
input:
863 269455309 42 29
output:
172561433
result:
ok single line: '172561433'
Test #14:
score: 5
Accepted
time: 1ms
memory: 3456kb
input:
28627 269441503 34 24
output:
180377871
result:
ok single line: '180377871'
Test #15:
score: 5
Accepted
time: 0ms
memory: 3556kb
input:
36656 67854541 25 6
output:
2429047
result:
ok single line: '2429047'
Test #16:
score: 5
Accepted
time: 1ms
memory: 3484kb
input:
27459 172755593 27 20
output:
73460042
result:
ok single line: '73460042'
Test #17:
score: 5
Accepted
time: 1ms
memory: 3448kb
input:
743268139 705178739 33 19
output:
311756018
result:
ok single line: '311756018'
Test #18:
score: 5
Accepted
time: 1ms
memory: 3460kb
input:
934248626 620145553 43 16
output:
121876656
result:
ok single line: '121876656'
Test #19:
score: 5
Accepted
time: 1ms
memory: 3512kb
input:
619290070 907487131 38 19
output:
213941765
result:
ok single line: '213941765'
Test #20:
score: 5
Accepted
time: 1ms
memory: 3528kb
input:
507684930 711845893 28 24
output:
419183631
result:
ok single line: '419183631'
Extra Test:
score: 0
Extra Test Passed