QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#656961#9476. 012 Griducup-team3161#AC ✓116ms35252kbC++204.3kb2024-10-19 13:56:422024-10-19 13:56:45

Judging History

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

  • [2024-10-19 13:56:45]
  • 评测
  • 测评结果:AC
  • 用时:116ms
  • 内存:35252kb
  • [2024-10-19 13:56:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ulll __uint128_t
#define eb emplace_back
#define po pop_back
#define mid ((l+r)/2)
#define mod FM.reduce
const int N=(1<<23)+5;
int fc[N],invfc[N];
int MOD,g1,lim,lim1,invl,r[N],g[2][N];
struct FastMod
{
	ull p,w;FastMod(ull p=2):p(p),w((ull)(((ulll)(1)<<64)/p)) {}
    ull reduce(ull x) {ull d=(ull)(((ulll)(w)*x)>>64),r=x-p*d;return r>=p?r-p:r;}
}FM;
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
void W(int &x,ll y) {x=mod(x+y);}
void W(int &x,ull y) {x=mod(x+y);}
int W1(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
int qpow(int x,int y)
{int res=1;for(;y;y>>=1,x=mod(1ll*x*x)) if(y&1) res=mod(1ll*res*x);return res;}
void initg()
{
	int t=MOD-1;vector<int> p;
	for(int i=2;i*i<=t;++i) if(!(t%i)) {p.eb(i);while(!(t%i)) t/=i;}
	if(t>1) p.eb(t);
	for(int i=2;;++i)
	{
		bool fl=1;for(auto j:p) if(qpow(i,(MOD-1)/j)==1) {fl=0;break;}
		if(fl) {g1=i;break;}
	}
}
void init(int n)
{
	int l=0;lim=1;while(lim<n) ++l,lim*=2;invl=qpow(lim,MOD-2);
	for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
	if(lim>lim1)
	{
		for(int i=1,t1,t2,t3,t4;i<lim;i*=2)
		{
			t1=qpow(g1,(MOD-1)/(i*2));t2=qpow(t1,MOD-2);t3=t4=1;
			for(int j=0;j<i;++j,t3=mod(1ll*t3*t1),t4=mod(1ll*t4*t2))
				g[0][i+j]=t3,g[1][i+j]=t4;
		}lim1=lim;
	}
}
void init1(int n)
{
    fc[0]=1;for(int i=1;i<=n;++i) fc[i]=mod(1ll*fc[i-1]*i);
    invfc[n]=qpow(fc[n],MOD-2);
    for(int i=n;i;--i) invfc[i-1]=mod(1ll*invfc[i]*i);
}
int bn(int x,int y) {return x<y || y<0?0:mod(mod(1ll*fc[x]*invfc[y])*invfc[x-y]);}
int calc(int i,int j) {return mod(mod(1ll*bn(i+j-2,i-1)*bn(i+j-2,i-1))-mod(1ll*bn(i+j-2,i)*bn(i+j-2,j))+MOD);}
struct Poly
{
	vector<int> a;Poly(vector<int> _a={}) {a=_a;}
	Poly mv(int x)
	{
		Poly res;res.a.resize(a.size()+x);
		copy(a.begin(),a.end(),res.a.begin()+x);return res;
	}
	void NTT(bool fl)
	{
		a.resize(lim);for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
		for(int i=1,t1,t2;i<lim;i*=2) for(int j=0;j<lim;j+=i*2) for(int k=0;k<i;++k)
		{
			t1=a[j+k];t2=mod(1ll*g[fl][i+k]*a[i+j+k]);
			a[j+k]=W1(t1,t2);a[i+j+k]=W1(t1,MOD-t2);
		}if(fl) for(int i=0;i<lim;++i) a[i]=mod(1ll*a[i]*invl); 
	}
	Poly operator + (const Poly &t) const
	{
		Poly res(a);if(a.size()<t.a.size()) res.a.resize(t.a.size());
		for(int i=0;i<t.a.size();++i) W(res.a[i],t.a[i]);return res;
	}
	Poly operator - (const Poly &t) const
	{
		Poly res(a);if(a.size()<t.a.size()) res.a.resize(t.a.size());
		for(int i=0;i<t.a.size();++i) W(res.a[i],MOD-t.a[i]);return res;
	}
	Poly operator * (Poly t) const
	{
		int n=a.size()+t.a.size()-1;Poly res(a);init(n);t.NTT(0);res.NTT(0);
		for(int i=0;i<lim;++i) res.a[i]=mod(1ll*res.a[i]*t.a[i]);res.NTT(1);
		res.a.resize(n);return res;
	}
	Poly operator * (int t) const
	{Poly res(a);for(auto &i:res.a) i=mod(1ll*i*t);return res;}
	Poly operator += (const Poly &t) {(*this)=(*this)+t;return *this;}
	Poly operator -= (const Poly &t) {(*this)=(*this)-t;return *this;}
	Poly operator *= (const Poly &t) {(*this)=(*this)*t;return *this;}
	Poly operator *= (int t) {for(auto &i:a) i=mod(1ll*i*t);return (*this);}
	Poly inv(int n)
	{
		if(a.size()<n) a.resize(n);if(n==1) return Poly({qpow(a[0],MOD-2)});
		Poly t=inv((n+1)/2),t1(vector<int>(a.begin(),a.begin()+n));
		init(n*2-1);t.NTT(0);t1.NTT(0);
		for(int i=0;i<lim;++i) t.a[i]=mod((2-mod(1ll*t.a[i]*t1.a[i])+MOD)*t.a[i]);
		t.NTT(1);t.a.resize(n);return t;
	}
	void deriv() {if(!a.empty()) {for(int i=1;i<a.size();++i) a[i-1]=mod(1ll*a[i]*i);a.po();}}
}f,f1;
int n,m,ans;
int main()
{
	MOD=998244353;FM=FastMod(MOD);initg();
    scanf("%d %d",&n,&m);ans=1;init1(1e6);

    f.a.resize(n);f1.a.resize(m);
    for(int i=0;i<n;++i) f.a[i]=mod(1ll*invfc[i]*invfc[i]);
    for(int i=0;i<m;++i) f1.a[i]=mod(1ll*invfc[i]*invfc[i]);
    f*=f1;
    for(int i=0;i<f.a.size();++i) W(ans,mod(1ll*f.a[i]*fc[i])*fc[i]);
    
    f.a.resize(n);f1.a.resize(m);
    for(int i=0;i<n;++i) f.a[i]=mod(1ll*invfc[i+1]*invfc[i-1]);
    for(int i=0;i<m;++i) f1.a[i]=mod(1ll*invfc[i+1]*invfc[i-1]);
    f*=f1;
    for(int i=0;i<f.a.size();++i) W(ans,mod(1ll*(MOD-f.a[i])*fc[i])*fc[i]);

    ans=mod(ans*2);
    W(ans,MOD-calc(n,m));

    for(int i=1;i<n;++i) W(ans,1ll*calc(i,m)*(n-i-1));
    for(int i=1;i<m;++i) W(ans,1ll*calc(n,i)*(m-i-1));
    printf("%d\n",ans);return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 14020kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 7ms
memory: 18208kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 100ms
memory: 34392kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 3ms
memory: 18148kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 7ms
memory: 18208kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 11ms
memory: 18144kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 7ms
memory: 18176kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 0ms
memory: 18220kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 7ms
memory: 18148kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 7ms
memory: 18432kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 3ms
memory: 18136kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 11ms
memory: 14048kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 11ms
memory: 18148kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 14ms
memory: 18392kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 13ms
memory: 14384kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 10ms
memory: 18344kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 9ms
memory: 18396kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 14ms
memory: 18400kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 10ms
memory: 18476kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 14ms
memory: 18396kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 14ms
memory: 18476kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 14ms
memory: 18396kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 10ms
memory: 18392kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

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

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 58ms
memory: 24136kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 57ms
memory: 28392kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 33ms
memory: 26956kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

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

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 59ms
memory: 29628kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 62ms
memory: 24108kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 54ms
memory: 23824kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 57ms
memory: 23848kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 59ms
memory: 24616kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 108ms
memory: 35252kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 116ms
memory: 33240kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

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

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 7ms
memory: 16176kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 32ms
memory: 26864kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 32ms
memory: 20836kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 7ms
memory: 18208kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed