QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#665651#9476. 012 GridKevin5307AC ✓430ms56940kbC++234.8kb2024-10-22 14:36:452024-10-22 14:36:56

Judging History

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

  • [2024-10-22 14:36:56]
  • 评测
  • 测评结果:AC
  • 用时:430ms
  • 内存:56940kb
  • [2024-10-22 14:36:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace Polynomial
{
	using ll=long long;
	using poly=vector<ll>;
	const ll mod=998244353;
	ll ksm(ll a,ll b)
	{
		ll ans=1;
		while(b)
		{
			if(b&1) ans=ans*a%mod;
			b>>=1;
			a=a*a%mod;
		}
		return ans;
	}
	inline int sz(const poly &p)
	{
		return p.size();
	}
	const poly operator +(const poly &a,const poly &b)
	{
		int p=sz(a),q=sz(b);
		int n=max(p,q);
		poly ret(n,0);
		for(int i=0;i<n;i++)
		{
			if(i<p) ret[i]+=a[i];
			if(i<q) ret[i]+=b[i];
			if(ret[i]>=mod) ret[i]-=mod;
		}
		return ret;
	}
	const poly operator -(const poly &a,const poly &b)
	{
		int p=sz(a),q=sz(b);
		int n=max(p,q);
		poly ret(n,0);
		for(int i=0;i<n;i++)
		{
			if(i<p) ret[i]+=a[i];
			if(i<q) ret[i]+=mod-b[i];
			if(ret[i]>=mod) ret[i]-=mod;
		}
		return ret;
	}
	poly operator *(poly a,poly b)
	{
		const ll g=3;
		int len=sz(a)+sz(b);
		int m=1;
		while(m<sz(a)+sz(b)) m*=2;
		a.resize(m);
		b.resize(m);
		vector<int> rev(m);
		for(int i=0;i<m;i++)
			rev[i]=(rev[i>>1]>>1)|((i&1)*(m>>1));
		for(int i=0;i<m;i++)
			if(rev[i]<i)
			{
				swap(a[i],a[rev[i]]);
				swap(b[i],b[rev[i]]);
			}
		for(int i=1;i<m;i<<=1)
		{
			ll gn=ksm(g,(mod-1)/i/2);
			for(int j=0;j<m;j+=(i<<1))
			{
				ll g0=1;
				for(int k=0;k<i;k++,g0=g0*gn%mod)
				{
					{
						ll x=a[j+k],y=g0*a[i+j+k]%mod;
						a[j+k]=(x+y)%mod;
						a[i+j+k]=(x+mod-y)%mod;
					}
					{
						ll x=b[j+k],y=g0*b[i+j+k]%mod;
						b[j+k]=(x+y)%mod;
						b[i+j+k]=(x+mod-y)%mod;
					}
				}
			}
		}
		for(int i=0;i<m;i++)
			a[i]=a[i]*b[i]%mod;
		for(int i=0;i<m;i++)
			if(rev[i]<i)
				swap(a[i],a[rev[i]]);
		for(int i=1;i<m;i<<=1)
		{
			ll gn=ksm(g,(mod-1)/i/2*(mod-2));
			for(int j=0;j<m;j+=(i<<1))
			{
				ll g0=1;
				for(int k=0;k<i;k++,g0=g0*gn%mod)
				{
					ll x=a[j+k],y=g0*a[i+j+k]%mod;
					a[j+k]=(x+y)%mod;
					a[i+j+k]=(x+mod-y)%mod;
				}
			}
		}
		ll val=ksm(m,mod-2);
		for(int i=0;i<m;i++)
			a[i]=a[i]*val%mod;
		a.resize(len-1);
		return a;
	}
	poly inv(poly p,int deg)
	{
		p.resize(deg);
		if(deg==1) return {ksm(p[0],mod-2)};
		poly w=inv(p,(deg+1)/2);
		poly g=w+w-p*w*w;
		g.resize(deg);
		return g;
	}
	poly deriv(poly p)
	{
		for(int i=0;i<sz(p);i++)
			p[i]=p[i]*i%mod;
		p.erase(p.begin());
		return p;
	}
	poly integ(poly p)
	{
		p.insert(p.begin(),0);
		for(int i=0;i<sz(p);i++)
			p[i]=p[i]*ksm(i,mod-2)%mod;
		return p;
	}
	poly ln(poly p)
	{
		return integ(deriv(p)*inv(p,sz(p)));
	}
	poly exp(poly p,int deg)
	{
		p.resize(deg);
		if(deg==1)
			return {1};
		poly g=exp(p,(deg+1)/2);
		g=g*(poly{1}-ln(g)+p);
		g.resize(deg);
		return g;
	}
	const poly operator %(poly a,poly b)
	{
		if(sz(a)<sz(b)) return a;
		int n=sz(a),m=sz(b);
		int d=n-m+1;
		poly a2=a,b2=b;
		reverse(a2.begin(),a2.end());
		reverse(b2.begin(),b2.end());
		a2.resize(d);
		b2.resize(d);
		poly q=a2*inv(b2,d);
		q.resize(d);
		reverse(q.begin(),q.end());
		q=a-b*q;
		q.resize(m-1);
		return q;
	}
	const poly operator /(poly a,poly b)
	{
		if(sz(a)<sz(b)) return a;
		int n=sz(a),m=sz(b);
		int d=n-m+1;
		poly a2=a,b2=b;
		reverse(a2.begin(),a2.end());
		reverse(b2.begin(),b2.end());
		a2.resize(d);
		b2.resize(d);
		poly q=a2*inv(b2,d);
		q.resize(d);
		reverse(q.begin(),q.end());
		return q;
	}
}
using namespace Polynomial;
ll fact[1001000],rfact[1001000];
ll C(int n,int k)
{
	if(k<0||k>n) return 0;
	return fact[n]*rfact[k]%mod*rfact[n-k]%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	fact[0]=rfact[0]=1;
	for(int i=1;i<1001000;i++)
	{
		fact[i]=fact[i-1]*i%mod;
		rfact[i]=rfact[i-1]*ksm(i,mod-2)%mod;
	}
	int h,w;
	cin>>h>>w;
	ll ans=0;
	poly f1(w+1),g1(h+1);
	for(int i=0;i<h;i++)
		g1[h-i-1]=rfact[h-i-1]*rfact[h-i]%mod;
	for(int j=0;j<w;j++)
		f1[w-j-1]=rfact[w-j-1]*rfact[w-j]%mod;
	poly h1=f1*g1;
	for(int i=0;i<sz(h1);i++)
		ans=(ans+h1[i]*fact[i]%mod*fact[i+1])%mod;
	poly f2(h+1),g2(h+1);
	for(int i=0;i<h;i++)
		f2[h-i]=1;
	for(int j=1;j<h;j++)
		g2[h-j]=1;
	poly h2=f2*g2;
	for(int i=h+1;i<sz(h2);i++)
	{
		int d=i-h;
		int d1=w;
		ans=(ans+h2[i]*fact[d+d1-2]%mod*fact[d+d1-1]%mod*rfact[d-1]%mod*rfact[d]%mod*rfact[d1-1]%mod*rfact[d1])%mod;
	}
	poly f3(w+1),g3(w+1);
	for(int i=1;i<w;i++)
		f3[w-i]=1;
	for(int j=0;j<w;j++)
		g3[w-j]=1;
	poly h3=f3*g3;
	for(int i=w+1;i<sz(h3);i++)
	{
		int d=i-w;
		int d1=h;
		ans=(ans+h3[i]*fact[d+d1-2]%mod*fact[d+d1-1]%mod*rfact[d-1]%mod*rfact[d]%mod*rfact[d1-1]%mod*rfact[d1])%mod;
	}
	poly f4(w+1),g4(h+1);
	for(int i=1;i<w;i++)
		f4[w-i-1]=rfact[w-i-1]*rfact[w-i]%mod;
	for(int j=1;j<h;j++)
		g4[h-j-1]=rfact[h-j-1]*rfact[h-j]%mod;
	poly h4=f4*g4;
	for(int i=0;i<sz(h4);i++)
		ans=(ans+h4[i]*fact[i]%mod*fact[i+1])%mod;
	cout<<(ans+2)%mod<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 105ms
memory: 19244kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 114ms
memory: 19248kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 412ms
memory: 54864kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 113ms
memory: 19432kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 102ms
memory: 19464kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 114ms
memory: 19240kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 106ms
memory: 19256kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 110ms
memory: 19252kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 107ms
memory: 19188kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 106ms
memory: 19200kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 110ms
memory: 19200kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 102ms
memory: 19436kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 109ms
memory: 19272kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 123ms
memory: 20316kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 120ms
memory: 19768kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 121ms
memory: 19868kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 117ms
memory: 19880kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 119ms
memory: 19932kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 121ms
memory: 20064kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 122ms
memory: 20144kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 123ms
memory: 20212kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 123ms
memory: 20236kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 120ms
memory: 20156kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 426ms
memory: 54184kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 250ms
memory: 36540kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 235ms
memory: 35100kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 184ms
memory: 28612kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 419ms
memory: 55632kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 267ms
memory: 37524kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 284ms
memory: 37080kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 222ms
memory: 34728kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 222ms
memory: 34844kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 269ms
memory: 38004kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 426ms
memory: 54836kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 430ms
memory: 56756kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 416ms
memory: 56940kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 109ms
memory: 19480kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 176ms
memory: 27792kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 172ms
memory: 27848kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 114ms
memory: 19252kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed