QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #825344 | #8428. Partition into Teams | wrkwrk | AC ✓ | 351ms | 27260kb | C++23 | 6.7kb | 2024-12-21 18:28:19 | 2024-12-21 18:28:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
bool st;
namespace _wrk{;
__uint128_t brt;
int mod;
struct modint{
int num;
modint(){
num=0;
}
modint(int x){
num=x%mod;
}
modint(long long x){
num=x%mod;
}
modint operator=(int x){
num=x%mod;
return (*this);
}
modint operator=(long long x){
num=x%mod;
return (*this);
}
modint operator=(modint x){
num=x.num;
return (*this);
}
modint operator+(modint c)const{
long long x=num+c.num;
return x>=mod?x-mod:x;
}
modint operator-(modint c)const{
long long x=num-c.num;
return x<0?x+mod:x;
}
modint operator*(modint c)const{
long long x=(long long)num*c.num;
x=x-mod*(brt*x>>64);
while(x>=mod)x-=mod;
return x;
}
modint fpof(long long x)const{
if(x<0)return inv().fpof(-x);
if(x==0)return 1;
auto c=((*this)*(*this)).fpof(x/2);
if(x&1)return c*(*this);
else return c;
}
struct modint_pow{
int pf;
modint_pow(int x){
pf=x;
}
modint_pow(modint x){
pf=x.num;
}
modint_pow operator+(modint_pow x){
return pf+x.pf;
}
};
modint_pow operator*(){
return modint_pow(num);
}
modint operator*(modint_pow x){
return (*this).fpof(x.pf);
}
modint inv()const{
return fpof(mod-2);
}
modint operator/(modint c){
return (*this)*c.inv();
}
operator int(){
return num;
}
modint operator+=(modint c){
return (*this)=(*this)+c;
}
modint operator-=(modint c){
return (*this)=(*this)-c;
}
modint operator*=(modint c){
return (*this)=(*this)*c;
}
modint operator/=(modint c){
return (*this)=(*this)/c;
}
modint operator-(){
return mod-num;
}
friend ostream& operator<<(ostream &w,modint &&x){
w<<x.num;
return w;
}
friend istream& operator>>(istream &w,modint &x){
w>>x.num;
x.num%=mod;
return w;
}
bool operator==(modint x){
return num==x.num;
}
};
template<int mod,class type>
modint operator+(type a,modint b){
return modint (a)+b;
}
template<int mod,class type>
modint operator-(type a,modint b){
return modint (a)-b;
}
template<int mod,class type>
modint operator*(type a,modint b){
return modint (a)*b;
}
template<int mod,class type>
modint operator/(type a,modint b){
return modint (a)/b;
}
#define int long long
template<class type,int N>
struct matrix{
type a[N+2][N+2];
int n;
type* operator[](int pos){
return a[pos];
}
matrix<type,N> operator*(matrix<type,N>b){
matrix<type,N>ans;
ans.n=n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
ans[i][j]+=a[i][k]*b[k][j];
}
}
}
return ans;
}
};
template<class type>
type fp(type a,int b){
if(b==0)return type();
if(b==1)return a;
type w=fp(a*a,b/2);
if(b%2)return w*a;
return w;
}
template<int N>
struct yw_int_array{
struct three21bit{
int a:21;
int b:21;
int c:21;
}a[N/3+2];
struct ref{
three21bit& s;
char type;
operator int(){
if(type==0)return s.a;
if(type==1)return s.b;
return s.c;
}
ref& operator=(int x){
if(type==0)s.a=x;
else if(type==1)s.b=x;
else s.c=x;
return (*this);
}
};
ref operator[](int pos){
char w=pos%3;
return {a[pos/3],(char)w};
}
};
template<class type,int N>
struct backup_array{
type name[N+5];
vector<vector<pair<int,int>>>cc;
void new_array(){
cc.push_back(vector<pair<int,int>>());
}
backup_array(){
cc.resize(1);
}
struct x{
int id;
type* name;
vector<vector<pair<int,int>>> &cc;
operator type(){
return name[id];
}
type operator=(type w){
cc.back().push_back({id,name[id]});
name[id]=w;
return w;
}
};
x operator[](int pos){
return {pos,name,cc};
}
void backup(){
reverse(cc.back().begin(),cc.back().end());
for(auto &x:cc.back()){
name[x.first]=x.second;
}
cc.pop_back();
}
};
template<class type,int N>
struct Math{
type jc[N+5],inv[N+5],invjc[N+5];
void init(){
jc[0]=jc[1]=inv[1]=invjc[1]=invjc[0]=1;
for(int i=2;i<=N;i++){
jc[i]=jc[i-1]*type(i);
}
invjc[N]=type(1)/jc[N];
for(int i=N-1;i>=2;i--){
invjc[i]=invjc[i+1]*type(i+1);
}
for(int i=1;i<=N;i++){
inv[i]=invjc[i]*jc[i-1];
}
}
type binom(int a,int b){
return jc[a]*jc[b].inv()*jc[a-b].inv();
}
type catalan(int n){
return binom(2*n,n)/type(n+1);
}
};
template<class type,int num,int maxnum>
struct pows{
type w[maxnum+5];
pows(){
w[0]=type(1);
for(int i=1;i<=maxnum;i++)w[i]=w[i-1]*type(num);
}
type operator[](int pos){
return w[pos];
}
};
#ifdef use_seg_tree
template<class type,class laz_type,int len>
struct segment_tree{
type a[len<<2];
laz_type laz[len<<2];
void pushup(int now){
PUSHUP_VALUE
}
void pushdown(int now,int l,int r){
PUSHDOWN_VALUE
}
void build(int now,int l,int r){
if(l+1==r){
FIRST_VALUE
return;
}
LAZ_CLEAR
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid,r);
pushup(now);
}
void do1(int now,int l,int r,int L,int R,...){
if(l+1!=r)pushdown(now,l,r);
if(R<=l||r<=L)return;
if(L<=l&&r<=R){
FULL_BLOCK_VALUE
return;
}
int mid=(l+r)>>1;
do1(now<<1,l,mid,L,R,...);
do1(now<<1|1,mid,r,L,R,...);
pushup(now);
}
void do1_one(int now,int l,int r,int p,...){
if(l+1!=r)pushdown(now,l,r);
if(l+1==r){
DO1_VALUE
return;
}
int mid=(l+r)>>1;
if(p<mid)do1_one(now<<1,l,mid,p,...);
else do1_one(now<<1|1,mid,r,p,...);
pushup(now);
}
type qu1(int now,int l,int r,int L,int R){
if(l+1!=r)pushdown(now,l,r);
if(R<=l||r<=L)return BASE_VALUE
if(L<=l&&r<=R)return a[now];
int mid=(l+r)>>1;
return RETURN_VALVE qu1(now<<1,l,mid,L,R)+qu1(now<<1|1,mid,r,L,R);
}
type qu1_one(int now,int l,int r,int p){
if(l+1!=r)pushdown(now,l,r);
if(l+1==r)return a[now];
int mid=(l+r)>>1;
if(p<mid)return qu1_one(now<<1,l,mid,p);
else return qu1_one(now<<1|1,mid,r,p);
}
};
#endif
//#define mod 998244353
#define mint modint
//pows<mint,2,10000007>tp;note the size
Math<mint,2000006>math;
//vector<int>g[1000006]
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n>>mod;
brt=((__uint128_t)(1)<<(64))/mod;
math.init();
mint res=1;
int ww=n;
while(n){
int w=n%mod;
mint su=0;
for(int i=0;i+i<=w;i++){
su+=math.binom(w,2*i)*math.binom(2*i,i);
// cout<<w<<' '<<2*i<<' '<<i<<' '<<su<<endl;
}
res*=su;
n/=mod;
}
// cout<<res<<'\n';
// cout<<res<<' '<<mint(3).fpof(ww)<<endl;
mint cww=(mint(3%mod).fpof(ww)-res)*mint((mod+1)/2);
cout<<cww;
return 0;
}
}
bool en;
signed main(){
#ifdef LOCAL_WRK
cerr<<"[Static Memory : "<<fixed<<((&st)-(&en))/1048576.0<<"MB]"<<endl;
#endif
return _wrk::main();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 55ms
memory: 26976kb
input:
5 5
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 51ms
memory: 27040kb
input:
5 7
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 55ms
memory: 26980kb
input:
789 97
output:
53
result:
ok 1 number(s): "53"
Test #4:
score: 0
Accepted
time: 58ms
memory: 27048kb
input:
98 23
output:
10
result:
ok 1 number(s): "10"
Test #5:
score: 0
Accepted
time: 55ms
memory: 27048kb
input:
398 7
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 55ms
memory: 27260kb
input:
272 31
output:
18
result:
ok 1 number(s): "18"
Test #7:
score: 0
Accepted
time: 55ms
memory: 27080kb
input:
920 199
output:
39
result:
ok 1 number(s): "39"
Test #8:
score: 0
Accepted
time: 51ms
memory: 27088kb
input:
390 5167
output:
1236
result:
ok 1 number(s): "1236"
Test #9:
score: 0
Accepted
time: 51ms
memory: 27252kb
input:
445 24337
output:
4546
result:
ok 1 number(s): "4546"
Test #10:
score: 0
Accepted
time: 51ms
memory: 26984kb
input:
28 586501
output:
269032
result:
ok 1 number(s): "269032"
Test #11:
score: 0
Accepted
time: 54ms
memory: 26968kb
input:
304 5
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 54ms
memory: 27040kb
input:
7158 41
output:
16
result:
ok 1 number(s): "16"
Test #13:
score: 0
Accepted
time: 59ms
memory: 27248kb
input:
8487 331
output:
148
result:
ok 1 number(s): "148"
Test #14:
score: 0
Accepted
time: 51ms
memory: 26980kb
input:
501 6763
output:
363
result:
ok 1 number(s): "363"
Test #15:
score: 0
Accepted
time: 52ms
memory: 26988kb
input:
3011 61129
output:
49319
result:
ok 1 number(s): "49319"
Test #16:
score: 0
Accepted
time: 58ms
memory: 27052kb
input:
7266 358159
output:
7643
result:
ok 1 number(s): "7643"
Test #17:
score: 0
Accepted
time: 54ms
memory: 27080kb
input:
360860 7
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 54ms
memory: 27048kb
input:
154939 19
output:
8
result:
ok 1 number(s): "8"
Test #19:
score: 0
Accepted
time: 54ms
memory: 26976kb
input:
813268 47
output:
40
result:
ok 1 number(s): "40"
Test #20:
score: 0
Accepted
time: 51ms
memory: 27052kb
input:
965601 1531
output:
1147
result:
ok 1 number(s): "1147"
Test #21:
score: 0
Accepted
time: 85ms
memory: 27260kb
input:
689332 78079
output:
17208
result:
ok 1 number(s): "17208"
Test #22:
score: 0
Accepted
time: 60ms
memory: 27040kb
input:
287719 34369
output:
15373
result:
ok 1 number(s): "15373"
Test #23:
score: 0
Accepted
time: 55ms
memory: 27040kb
input:
439237583 7
output:
6
result:
ok 1 number(s): "6"
Test #24:
score: 0
Accepted
time: 51ms
memory: 27248kb
input:
319142531 79
output:
21
result:
ok 1 number(s): "21"
Test #25:
score: 0
Accepted
time: 55ms
memory: 26984kb
input:
592330255 631
output:
530
result:
ok 1 number(s): "530"
Test #26:
score: 0
Accepted
time: 57ms
memory: 26984kb
input:
164278463 4517
output:
3038
result:
ok 1 number(s): "3038"
Test #27:
score: 0
Accepted
time: 61ms
memory: 27216kb
input:
753671285 65371
output:
22369
result:
ok 1 number(s): "22369"
Test #28:
score: 0
Accepted
time: 351ms
memory: 27084kb
input:
289665297 663127
output:
168503
result:
ok 1 number(s): "168503"
Test #29:
score: 0
Accepted
time: 51ms
memory: 27040kb
input:
350585676619 7
output:
5
result:
ok 1 number(s): "5"
Test #30:
score: 0
Accepted
time: 51ms
memory: 27252kb
input:
4283693890775 31
output:
1
result:
ok 1 number(s): "1"
Test #31:
score: 0
Accepted
time: 55ms
memory: 26984kb
input:
1234727503131 151
output:
67
result:
ok 1 number(s): "67"
Test #32:
score: 0
Accepted
time: 55ms
memory: 26980kb
input:
9399186742989 1327
output:
678
result:
ok 1 number(s): "678"
Test #33:
score: 0
Accepted
time: 59ms
memory: 27084kb
input:
1409645481800 8719
output:
1939
result:
ok 1 number(s): "1939"
Test #34:
score: 0
Accepted
time: 218ms
memory: 27020kb
input:
3782178721166 552859
output:
458256
result:
ok 1 number(s): "458256"
Test #35:
score: 0
Accepted
time: 59ms
memory: 26924kb
input:
827235816874722972 5
output:
2
result:
ok 1 number(s): "2"
Test #36:
score: 0
Accepted
time: 55ms
memory: 26988kb
input:
648249960855836992 61
output:
56
result:
ok 1 number(s): "56"
Test #37:
score: 0
Accepted
time: 55ms
memory: 27036kb
input:
467138518199434341 563
output:
202
result:
ok 1 number(s): "202"
Test #38:
score: 0
Accepted
time: 55ms
memory: 27252kb
input:
616207494477524619 653
output:
95
result:
ok 1 number(s): "95"
Test #39:
score: 0
Accepted
time: 67ms
memory: 27020kb
input:
129689263663821851 34403
output:
30422
result:
ok 1 number(s): "30422"
Test #40:
score: 0
Accepted
time: 225ms
memory: 26976kb
input:
605206340470214709 479971
output:
381982
result:
ok 1 number(s): "381982"