QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710164#9476. 012 GridWrongAnswer_90AC ✓113ms62864kbC++237.6kb2024-11-04 18:55:302024-11-04 18:55:31

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 18:55:31]
  • 评测
  • 测评结果:AC
  • 用时:113ms
  • 内存:62864kb
  • [2024-11-04 18:55:30]
  • 提交

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