QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#710164 | #9476. 012 Grid | WrongAnswer_90 | AC ✓ | 113ms | 62864kb | C++23 | 7.6kb | 2024-11-04 18:55:30 | 2024-11-04 18:55:31 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define FastI
#define FastO
#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[200000030],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
int x,y,z;
tup(int X=0,int Y=0,int Z=0)
{x=X,y=Y,z=Z;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,200000030,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
template<typename T> inline void write(T x,char ch=' ')
{
if(is_same<char,T>::value)putchar(x);
else
{
if(x<0)x=-x,putchar('-');
static char st[40];
int top=0;
do st[top++]=x%10+'0',x/=10;while(x);
while(top)putchar(st[--top]);
}
ch!='~'?putchar(ch):0;
}
inline void write(const char*x,char ch=' ')
{
for(int i=0;x[i]!='\0';++i)putchar(x[i]);
ch!='~'?putchar(ch):0;
}
inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
inline void read(char s[])
{
int len=0;char st;
do st=getchar();while(st=='\n'||st==' ');
s[++len]=st,st=getchar();
while(st!='\n'&&st!=' '&&st!='\r'&&st!='\0')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
char ch=getchar();s=0;
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
bool tf=(ch=='-'&&(ch=getchar()));
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
s=tf?-s:s;
}
inline void edl(){putchar('\n');}
template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
#ifdef FastO
struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
#endif
}
using namespace FastIO;
namespace MTool
{
inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
inline int sqr(int a){return 1ll*a*a%MOD;}
inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
namespace Poly
{
inline vi fix(vi A,int n){return A.resize(n),A;}
const int MAXN=2000000;
int Shape,VBL,Invn[MAXN],R[MAXN<<1],Prt[MAXN<<1],P0[50010],P1[50010];
inline void init()
{
P0[0]=P1[0]=1,VBL=ceil(sqrt(MOD)),Invn[0]=1;
for(int i=1;i<MAXN;++i)Invn[i]=Cmul(Invn[i-1],i);
int tmp=power(Invn[MAXN-1],MOD-2);
for(int i=MAXN-1;i>=1;--i)Invn[i]=Cmul(tmp,Invn[i-1]),Mmul(tmp,i);
for(int i=1;i<=VBL;++i)P0[i]=Cmul(P0[i-1],Root);
for(int i=1;i<=VBL;++i)P1[i]=Cmul(P1[i-1],P0[VBL]);
}
inline int powerr(int x){return Cmul(P0[x%VBL],P1[x/VBL]);}
inline void NTT(vi&A,int n,int opt)
{
static ull B[MAXN<<1],iv;
A.resize(n);
for(int i=0;i<n;++i)B[i]=A[R[i]];
for(int mid=1;mid<n;mid<<=1)
{
for(int j=0;j<n;j+=mid<<1)
{
for(int k=j;k<j+mid;++k)
{
ull x=B[k],y=Prt[mid+k-j]*B[k+mid]%MOD;
B[k]=x+y,B[k+mid]=x+MOD-y;
}
}
}
if(opt)for(int i=0;i<n;++i)A[i]=B[i]%MOD;
else
{
reverse(B+1,B+n),iv=power(n,MOD-2);
for(int i=0;i<n;++i)A[i]=Cmul(B[i]%MOD,iv);
}
}
inline void init(int lim)
{
if(lim==Shape)return;
int n=lim/2;
for(int i=0;i<lim;++i)R[i]=(R[i>>1]>>1)|((i&1)?n:0);
for(int i=1;i<lim;i<<=1)
{
int wm=powerr((MOD-1)/(i<<1));Prt[i]=1;
for(int j=1;j<i;++j)Prt[i+j]=Cmul(Prt[i+j-1],wm);
}
Shape=lim;
}
inline vi FFT(vi A,vi B)
{
int n=A.size(),m=B.size(),N=1;
while(N<=n+m)N<<=1;
init(N),NTT(A,N,1),NTT(B,N,1);
for(int i=0;i<N;++i)A[i]=Cmul(A[i],B[i]);
return NTT(A,N,0),A.resize(n+m-1),A;
}
}
using namespace Poly;
const int N=400000;
int fr[N+10],inv[N+10];
inline int C(int n,int m){return m<0||m>n?0:Cmul(fr[n],inv[m],inv[n-m]);}
inline void init(int n=N)
{
fr[0]=inv[0]=1;
for(int i=1;i<=n;++i)fr[i]=Cmul(fr[i-1],i);
inv[n]=power(fr[n],MOD-2);
for(int i=n-1;i>0;--i)inv[i]=Cmul(inv[i+1],i+1);
}
int n,m;
inline int calc(int n,int m)
{
return Cdel(Cmul(C(n-1+m-1,n-1),C(n-1+m-1,n-1)),
Cmul(C(n-1+m-1,n-2),C(n-1+m-1,n)));
}
void mian()
{
read(n,m);
int ans=0;
for(int i=1;i<=n;++i)Madd(ans,Cmul(n-i+1,calc(i,m)));
for(int i=1;i<=m;++i)Madd(ans,Cmul(m-i+1,calc(n,i)));
Mdel(ans,calc(n,m));
if(n>1&&m>1)
{
vi F(n-1),G(m-1);
for(int i=0;i<=n-2;++i)F[i]=Cmul(inv[i],inv[i]);
for(int i=0;i<=m-2;++i)G[i]=Cmul(inv[i],inv[i]);
F=FFT(F,G);
for(int i=0;i<=n-2+m-2;++i)Madd(ans,Cmul(2,fr[i],fr[i],F[i]));
F.resize(n-1),F[0]=G[0]=0;
for(int i=1;i<=n-2;++i)F[i]=Cmul(inv[i-1],inv[i+1]);
for(int i=1;i<=m-2;++i)G[i]=Cmul(inv[i-1],inv[i+1]);
F=FFT(F,G);
for(int i=0;i<=n-2+m-2;++i)Mdel(ans,Cmul(2,fr[i],fr[i],F[i]));
}
write(Cadd(ans,2),'\n');
}
inline void Mian()
{
WrongAnswer_90::init();
Poly::init();
int T=1;
// read(T);
while(T--)mian();
}
}
bool ED;
signed main()
{
// ios::sync_with_stdio(0);
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
double st=clock();
WrongAnswer_90::Mian();
double ed=clock();
cerr<<endl;
cerr<<"Time: "<<ed-st<<" ms\n";
cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 21ms
memory: 33416kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 24ms
memory: 32188kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 96ms
memory: 59616kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 22ms
memory: 32404kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 25ms
memory: 32448kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 24ms
memory: 32896kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 20ms
memory: 31476kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 24ms
memory: 32920kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 16ms
memory: 33440kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 16ms
memory: 33116kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 25ms
memory: 32768kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 18ms
memory: 34544kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 14ms
memory: 33304kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 18ms
memory: 32200kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 18ms
memory: 33488kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 21ms
memory: 33172kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 26ms
memory: 33512kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 18ms
memory: 32600kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 18ms
memory: 32292kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 26ms
memory: 33376kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 19ms
memory: 33488kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 23ms
memory: 32096kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 30ms
memory: 34788kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 113ms
memory: 59416kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 48ms
memory: 46664kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 56ms
memory: 46860kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 31ms
memory: 37688kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 79ms
memory: 61508kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 58ms
memory: 47788kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 48ms
memory: 47232kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 55ms
memory: 44312kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 51ms
memory: 44424kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 49ms
memory: 47740kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 86ms
memory: 60016kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 92ms
memory: 61308kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 98ms
memory: 62864kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 12ms
memory: 31952kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 20ms
memory: 31316kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 28ms
memory: 39864kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 17ms
memory: 32428kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed