QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #823209 | #8428. Partition into Teams | peimuda | AC ✓ | 11ms | 16180kb | C++11 | 833b | 2024-12-20 20:29:46 | 2024-12-20 20:29:46 |
Judging History
answer
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
ll jc[1000006];
ll jy[1000006];
ll pw(ll a,ll b,ll m)
{
ll r=1;
while(b)
{
if(b&1) r=r*a%m;
a=a*a%m;
b>>=1;
}
return r;
}
ll sol(ll a,ll m)
{
ll rt=0;
for(int i=0;i*2<=a;i++) rt+=jc[a]*jy[i]%m*jy[i]%m*jy[a-i*2]%m;
return rt%m;
}
int main()
{
ios_base::sync_with_stdio(0);
ll n;
ll m;
cin>>n>>m;
jc[0]=1;
for(int i=1;i<m;i++) jc[i]=jc[i-1]*i%m;
jy[m-1]=m-1;
for(int i=m-2;i>=0;i--) jy[i]=jy[i+1]*(i+1)%m;
ll ans=1;
ll gp=pw(3,n,m),hf=(m+1)/2;
while(n) ans=ans*sol(n%m,m)%m,n/=m;
cout<<(gp+m-ans)*hf%m<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5688kb
input:
5 5
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
5 7
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5656kb
input:
789 97
output:
53
result:
ok 1 number(s): "53"
Test #4:
score: 0
Accepted
time: 0ms
memory: 5732kb
input:
98 23
output:
10
result:
ok 1 number(s): "10"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5688kb
input:
398 7
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
272 31
output:
18
result:
ok 1 number(s): "18"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
920 199
output:
39
result:
ok 1 number(s): "39"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
390 5167
output:
1236
result:
ok 1 number(s): "1236"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5852kb
input:
445 24337
output:
4546
result:
ok 1 number(s): "4546"
Test #10:
score: 0
Accepted
time: 10ms
memory: 16180kb
input:
28 586501
output:
269032
result:
ok 1 number(s): "269032"
Test #11:
score: 0
Accepted
time: 0ms
memory: 5744kb
input:
304 5
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 0ms
memory: 5652kb
input:
7158 41
output:
16
result:
ok 1 number(s): "16"
Test #13:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
8487 331
output:
148
result:
ok 1 number(s): "148"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5780kb
input:
501 6763
output:
363
result:
ok 1 number(s): "363"
Test #15:
score: 0
Accepted
time: 2ms
memory: 8216kb
input:
3011 61129
output:
49319
result:
ok 1 number(s): "49319"
Test #16:
score: 0
Accepted
time: 6ms
memory: 12292kb
input:
7266 358159
output:
7643
result:
ok 1 number(s): "7643"
Test #17:
score: 0
Accepted
time: 0ms
memory: 5752kb
input:
360860 7
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 5596kb
input:
154939 19
output:
8
result:
ok 1 number(s): "8"
Test #19:
score: 0
Accepted
time: 0ms
memory: 5660kb
input:
813268 47
output:
40
result:
ok 1 number(s): "40"
Test #20:
score: 0
Accepted
time: 0ms
memory: 5696kb
input:
965601 1531
output:
1147
result:
ok 1 number(s): "1147"
Test #21:
score: 0
Accepted
time: 0ms
memory: 8156kb
input:
689332 78079
output:
17208
result:
ok 1 number(s): "17208"
Test #22:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
287719 34369
output:
15373
result:
ok 1 number(s): "15373"
Test #23:
score: 0
Accepted
time: 1ms
memory: 5556kb
input:
439237583 7
output:
6
result:
ok 1 number(s): "6"
Test #24:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
319142531 79
output:
21
result:
ok 1 number(s): "21"
Test #25:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
592330255 631
output:
530
result:
ok 1 number(s): "530"
Test #26:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
164278463 4517
output:
3038
result:
ok 1 number(s): "3038"
Test #27:
score: 0
Accepted
time: 2ms
memory: 7968kb
input:
753671285 65371
output:
22369
result:
ok 1 number(s): "22369"
Test #28:
score: 0
Accepted
time: 10ms
memory: 15000kb
input:
289665297 663127
output:
168503
result:
ok 1 number(s): "168503"
Test #29:
score: 0
Accepted
time: 1ms
memory: 5556kb
input:
350585676619 7
output:
5
result:
ok 1 number(s): "5"
Test #30:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
4283693890775 31
output:
1
result:
ok 1 number(s): "1"
Test #31:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
1234727503131 151
output:
67
result:
ok 1 number(s): "67"
Test #32:
score: 0
Accepted
time: 1ms
memory: 7664kb
input:
9399186742989 1327
output:
678
result:
ok 1 number(s): "678"
Test #33:
score: 0
Accepted
time: 1ms
memory: 5736kb
input:
1409645481800 8719
output:
1939
result:
ok 1 number(s): "1939"
Test #34:
score: 0
Accepted
time: 11ms
memory: 15568kb
input:
3782178721166 552859
output:
458256
result:
ok 1 number(s): "458256"
Test #35:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
827235816874722972 5
output:
2
result:
ok 1 number(s): "2"
Test #36:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
648249960855836992 61
output:
56
result:
ok 1 number(s): "56"
Test #37:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
467138518199434341 563
output:
202
result:
ok 1 number(s): "202"
Test #38:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
616207494477524619 653
output:
95
result:
ok 1 number(s): "95"
Test #39:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
129689263663821851 34403
output:
30422
result:
ok 1 number(s): "30422"
Test #40:
score: 0
Accepted
time: 5ms
memory: 13892kb
input:
605206340470214709 479971
output:
381982
result:
ok 1 number(s): "381982"