QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#19461 | #1816. Multiple Parentheses | foreverlasting | AC ✓ | 150ms | 27220kb | C++20 | 4.4kb | 2022-01-31 14:46:45 | 2022-05-06 05:31:15 |
Judging History
answer
//2022.1.31 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res int
#define LL long long
#define Inf 0x3f3f3f3f
#define sup 0x7fffffff
#define inf 0x3f3f3f3f
#define INF 2000000000000000000
//#define unl __int128
#define eps 1e-10
#define RG
#define db double
#define pc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
//#define poly vector<int>
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define uint unsigned int
#define lowbit(x) ((x)&-(x))
#define gc getchar
#define ld long db
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline int gc() {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
//char sr[1<<21],z[20];
//int C=-1,Z=0;
//inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
//inline void print(RG LL x){
// if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
// while(z[++Z]=x%10+48,x/=10);
// while(sr[++C]=z[Z],--Z);
//}
template <typename T> inline void Read(T &x) {
res c=gc();
bool f=false;
for(x=0;!isdigit(c);c=gc())if(c=='-')f=true;
for(;isdigit(c);c=gc())x=x*10+c-'0';
if(f)x=-x;
}
inline int read() {
res s=0,ch=gc(),w=1;
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
else if(ch==EOF)break;
ch=gc();
}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s*w;
}
inline LL Read() {
RG LL s=0;
res ch=gc(),w=1;
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
else if(ch==EOF)break;
ch=gc();
}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s*w;
}
inline void write(RG __int128 x){
if(x>10)write(x/10);
putchar(int(x%10)+'0');
}
const int kcz=998244353;
const int G=3,GI=332748118;
//inline void add(res &x,const res &y){
// x+=y,x>=kcz?x-=kcz:1;
//}
//inline int Add(const res &x,const res &y){
// return x+y>=kcz?x+y-kcz:x+y;
//}
//inline int mul(const res &x,const res &y){
// return int(1ll*x*y%kcz);
//}
#define add(x,y) ((x)+=(y),(x)>=kcz?(x)-=kcz:1)
#define Add(x,y) ((x)+(y)>=kcz?(x)+(y)-kcz:(x)+(y))
#define mul(x,y) (int)((LL)(x)*(y)%kcz)
#define Mul(x,y,d) (int)((ull)(x)*(y)/(d)%kcz)
inline int qpow(res x,res y=kcz-2){
res ret=1;
while(y){
if(y&1)ret=mul(ret,x);
x=mul(x,x),y>>=1;
}
return ret;
}
inline int qpow(res x,res y,const res &ljc){
res ret=1;
while(y){
if(y&1)ret=(int)(1ll*ret*x%ljc);
x=(int)(1ll*x*x%ljc),y>>=1;
}
return ret;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//cloclim_t start=cloclim();
//inline void clim(){
// if(1.0*(cloclim()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
//2022.1.31 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
const int N=3e6+10;
namespace MAIN{
int n,m,k;
int fac[N],inv[N];
inline int C(const res &x,const res &y){
return mul(fac[x],mul(inv[y],inv[x-y]));
}
inline void MAIN(){
fac[0]=fac[1]=inv[0]=inv[1]=1;
n=read(),m=read(),k=read();
for(res i=2;i<=n+2*m;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
for(res i=2;i<=n+2*m;i++)inv[i]=mul(inv[i-1],inv[i]);
res ans=0;
res K=mul(C(2*k,k-1),qpow(k)),ret=1;
for(res i=0;i<=n;i++){
if(i*k>m)break;
if(i*k==m){
if(i&1)add(ans,kcz-mul(C(n,i),ret));
else add(ans,mul(C(n,i),ret));
}
else {
if(i&1)add(ans,kcz-mul(mul(C(n,i),ret),mul(C(2*m+n-2*k*i-i-1,m-k*i-1),mul(n-i,qpow(m-k*i)))));
else add(ans,mul(mul(C(n,i),ret),mul(C(2*m+n-2*k*i-i-1,m-k*i-1),mul(n-i,qpow(m-k*i)))));
}
ret=mul(ret,K);
}
printf("%d\n",ans);
}
}
int main(){
// srand(time(0));
// freopen("18_linked_list.in","r",stdin);
// freopen("1.out","w",stdout);
res Case=1;
for(res T=1;T<=Case;T++)MAIN::MAIN();
// Ot();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 5632kb
input:
2 2 1
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 3ms
memory: 5796kb
input:
1 1 1
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 3ms
memory: 5712kb
input:
24 120 30
output:
379268651
result:
ok answer is '379268651'
Test #4:
score: 0
Accepted
time: 6ms
memory: 5780kb
input:
1451 1598 1130
output:
884873572
result:
ok answer is '884873572'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5764kb
input:
1324 1742 1033
output:
856733047
result:
ok answer is '856733047'
Test #6:
score: 0
Accepted
time: 2ms
memory: 5720kb
input:
1378 1614 1335
output:
869903701
result:
ok answer is '869903701'
Test #7:
score: 0
Accepted
time: 0ms
memory: 5652kb
input:
1071 1907 1281
output:
327700529
result:
ok answer is '327700529'
Test #8:
score: 0
Accepted
time: 2ms
memory: 5764kb
input:
1204 1337 1277
output:
475981175
result:
ok answer is '475981175'
Test #9:
score: 0
Accepted
time: 3ms
memory: 5748kb
input:
146 246 100
output:
404402509
result:
ok answer is '404402509'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5788kb
input:
226 183 144
output:
351921989
result:
ok answer is '351921989'
Test #11:
score: 0
Accepted
time: 0ms
memory: 5676kb
input:
234 287 158
output:
658959115
result:
ok answer is '658959115'
Test #12:
score: 0
Accepted
time: 0ms
memory: 5724kb
input:
242 156 122
output:
325586111
result:
ok answer is '325586111'
Test #13:
score: 0
Accepted
time: 3ms
memory: 5720kb
input:
168 271 135
output:
181613866
result:
ok answer is '181613866'
Test #14:
score: 0
Accepted
time: 3ms
memory: 5768kb
input:
22 25 1
output:
684860973
result:
ok answer is '684860973'
Test #15:
score: 0
Accepted
time: 0ms
memory: 5720kb
input:
45 22 15
output:
217501624
result:
ok answer is '217501624'
Test #16:
score: 0
Accepted
time: 3ms
memory: 5768kb
input:
47 29 16
output:
690840771
result:
ok answer is '690840771'
Test #17:
score: 0
Accepted
time: 3ms
memory: 5712kb
input:
2 25 25
output:
660660974
result:
ok answer is '660660974'
Test #18:
score: 0
Accepted
time: 0ms
memory: 5756kb
input:
32 34 11
output:
133387056
result:
ok answer is '133387056'
Test #19:
score: 0
Accepted
time: 3ms
memory: 9080kb
input:
88196 118335 104471
output:
7192211
result:
ok answer is '7192211'
Test #20:
score: 0
Accepted
time: 4ms
memory: 8796kb
input:
142215 57117 51272
output:
627598793
result:
ok answer is '627598793'
Test #21:
score: 0
Accepted
time: 5ms
memory: 8692kb
input:
102255 60360 51525
output:
447649003
result:
ok answer is '447649003'
Test #22:
score: 0
Accepted
time: 2ms
memory: 8896kb
input:
132449 83413 54230
output:
215816803
result:
ok answer is '215816803'
Test #23:
score: 0
Accepted
time: 3ms
memory: 6716kb
input:
68499 95762 77190
output:
393029560
result:
ok answer is '393029560'
Test #24:
score: 0
Accepted
time: 150ms
memory: 21584kb
input:
751951 751951 1
output:
804170883
result:
ok answer is '804170883'
Test #25:
score: 0
Accepted
time: 11ms
memory: 11220kb
input:
804420 1962 410
output:
869056555
result:
ok answer is '869056555'
Test #26:
score: 0
Accepted
time: 19ms
memory: 11212kb
input:
828607 63739 13
output:
926542030
result:
ok answer is '926542030'
Test #27:
score: 0
Accepted
time: 7ms
memory: 9848kb
input:
472167 20529 23
output:
142703540
result:
ok answer is '142703540'
Test #28:
score: 0
Accepted
time: 74ms
memory: 12224kb
input:
363438 363438 1
output:
764563597
result:
ok answer is '764563597'
Test #29:
score: 0
Accepted
time: 54ms
memory: 27088kb
input:
1000000 1000000 628333
output:
283487375
result:
ok answer is '283487375'
Test #30:
score: 0
Accepted
time: 46ms
memory: 27220kb
input:
1000000 1000000 900084
output:
651386967
result:
ok answer is '651386967'
Test #31:
score: 0
Accepted
time: 48ms
memory: 27220kb
input:
1000000 1000000 27328
output:
621963453
result:
ok answer is '621963453'
Test #32:
score: 0
Accepted
time: 52ms
memory: 27132kb
input:
1000000 1000000 538409
output:
997879100
result:
ok answer is '997879100'
Test #33:
score: 0
Accepted
time: 62ms
memory: 27132kb
input:
1000000 1000000 928121
output:
964724707
result:
ok answer is '964724707'
Test #34:
score: 0
Accepted
time: 26ms
memory: 21316kb
input:
685624 665877 563708
output:
257429683
result:
ok answer is '257429683'
Test #35:
score: 0
Accepted
time: 38ms
memory: 25280kb
input:
692290 942095 553970
output:
82511143
result:
ok answer is '82511143'
Test #36:
score: 0
Accepted
time: 25ms
memory: 22160kb
input:
579579 765702 631728
output:
954001361
result:
ok answer is '954001361'
Test #37:
score: 0
Accepted
time: 31ms
memory: 19524kb
input:
756854 634736 567170
output:
393747028
result:
ok answer is '393747028'
Test #38:
score: 0
Accepted
time: 54ms
memory: 25328kb
input:
649175 997874 511181
output:
242172216
result:
ok answer is '242172216'
Test #39:
score: 0
Accepted
time: 54ms
memory: 26268kb
input:
786431 1000000 999999
output:
627359027
result:
ok answer is '627359027'