QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#658795#9476. 012 Griducup-team3510#AC ✓195ms33812kbC++144.9kb2024-10-19 17:37:472024-10-19 17:37:50

Judging History

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

  • [2024-10-19 17:37:50]
  • 评测
  • 测评结果:AC
  • 用时:195ms
  • 内存:33812kb
  • [2024-10-19 17:37:47]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int fac[1 << 19], inv[1 << 19], Inv[1 << 19];
int omg[1 << 20], rev[1 << 20];
int F[1 << 19], X[1 << 19], Y[1 << 19], Z[1 << 19];
int ans[1 << 19];
int qpow(int x, int y)
{
    int ans = 1;
    while(y)
    {
        if(y & 1)
            ans = (ll)ans * x % mod;
        x = (ll)x * x % mod;
        y >>= 1;
    }
    return ans;
}
void prep(int n)
{
    int i, j, w, m = (1 << n) - 1;
    fac[0] = 1;
    for(i = 1; i <= m; i++)
        fac[i] = (ll)fac[i - 1] * i % mod;
    inv[m] = qpow(fac[m], mod - 2);
    for(i = m; i >= 1; i--)
        inv[i - 1] = (ll)inv[i] * i % mod;
    for(i = 1; i <= m; i++)
        Inv[i] = (ll)inv[i] * fac[i - 1] % mod;
    for(i = 0; i <= n; i++)
    {
        for(j = 1; j < (1 << i); j++)
            rev[(1 << i) + j] = (rev[(1 << (i - 1)) + (j >> 1)] | ((j & 1) << (i - 1)));
        omg[1 << i] = 1;
        w = qpow(3, (mod - 1) >> i);
        for(j = 1; j < (1 << i); j++)
            omg[(1 << i) + j] = (ll)omg[(1 << i) + j - 1] * w % mod;
    }
}
void ntt(int *A, int n, bool t)
{
    int i, j, k, w;
    for(i = 0; i < (1 << n); i++)
        if(i < rev[(1 << n) + i])
            swap(A[i], A[rev[(1 << n) + i]]);
    for(i = 0; i < n; i++)
        for(j = 0; j < (1 << n); j += (2 << i))
            for(k = 0; k < (1 << i); k++)
            {
                w = (ll)omg[(2 << i) + k] * A[(1 << i) + j + k] % mod;
                A[(1 << i) + j + k] = (A[j + k] + mod - w) % mod;
                A[j + k] = (A[j + k] + w) % mod;
            }
    if(t)
    {
        for(i = 1; i < (1 << n); i++)
            if(i < (1 << n) - i)
                swap(A[i], A[(1 << n) - i]);
        w = qpow(1 << n, mod - 2);
        for(i = 0; i < (1 << n); i++)
            A[i] = (ll)A[i] * w % mod;
    }
}
struct poly
{
    vector<int> c;
    poly()
    {
        c.clear();
    }
    friend poly operator * (poly f, poly g)
    {
        if(f.c.empty() || g.c.empty())
            return poly();
        poly h;
        int i, l = 0;
        while((f.c.size() + g.c.size()) >> l)
            l++;
        memset(X, 0, 4 << l);
        memset(Y, 0, 4 << l);
        for(i = 0; i < f.c.size(); i++)
            X[i] = f.c[i];
        for(i = 0; i < g.c.size(); i++)
            Y[i] = g.c[i];
        ntt(X, l, 0);
        ntt(Y, l, 0);
        for(i = 0; i < (1 << l); i++)
            X[i] = (ll)X[i] * Y[i] % mod;
        ntt(X, l, 1);
        h.c.resize(f.c.size() + g.c.size() - 1);
        for(i = 0; i < h.c.size(); i++)
            h.c[i] = X[i];
        return h;
    }
    friend poly operator / (poly f, poly g)
    {
        if(f.c.empty() || g.c.empty())
            return poly();
        poly h;
        int i, l = 0;
        while((f.c.size() + g.c.size()) >> l)
            l++;
        memset(X, 0, 4 << l);
        memset(Y, 0, 4 << l);
        for(i = 0; i < f.c.size(); i++)
            X[i] = f.c[i];
        for(i = 0; i < g.c.size(); i++)
            Y[i] = g.c[g.c.size() - 1 - i];
        ntt(X, l, 0);
        ntt(Y, l, 0);
        for(i = 0; i < (1 << l); i++)
            X[i] = (ll)X[i] * Y[i] % mod;
        ntt(X, l, 1);
        h.c.resize(f.c.size());
        for(i = 0; i < h.c.size(); i++)
            h.c[i] = X[i + g.c.size() - 1];
        return h;
    }
};
int n,m,s[400010];
inline int C(int n,int m)
{
	return n<m?0:(long long)
	s[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	prep(19);
	cin>>n>>m;
	for(int i=s[0]=inv[0]=1;i<=n+m;i++)
	{
		s[i]=(long long)s[i-1]*i%mod;
		inv[i]=qpow(s[i],mod-2);
	}
	__int128_t ans=0;
	ans+=(long long)C(n+m-2,n-1)*C(n+m-2,n-1);
	ans-=(long long)C(n+m-2,n)*C(n+m-2,m);
	for(int i=1;i<n;i++)
	{
		ans+=2ll*C(m+i-2,m-1)*C(m+i-2,m-1);
		ans-=2ll*C(m+i-2,i)*C(m+i-2,m);
	}
	for(int i=1;i<m;i++)
	{
		ans+=2ll*C(n+i-2,n-1)*C(n+i-2,n-1);
		ans-=2ll*C(n+i-2,i)*C(n+i-2,n);
	}
	vector<int> v1(n-1),v2(m-1);
	for(int i=0;i<n-1;i++)
	{
		v1[i]=(long long)
		inv[i]*inv[i]%mod;
	}
	for(int i=0;i<m-1;i++)
	{
		v2[i]=(long long)
		inv[i]*inv[i]%mod;
	}
	poly a,b,c;
	a.c=v1,b.c=v2,c=a*b;
	for(int i=0;i<c.c.size();i++)
	{
		ans+=2ll*s[i]*s[i]%mod*c.c[i];
	}
	for(int i=0;i<n-1;i++)
	{
		v1[i]=i?(long long)
		inv[i+1]*inv[i-1]%mod:0;
	}
	for(int i=0;i<m-1;i++)
	{
		v2[i]=i?(long long)
		inv[i+1]*inv[i-1]%mod:0;
	}
	a.c=v1,b.c=v2,c=a*b;
	for(int i=0;i<c.c.size();i++)
	{
		ans-=2ll*s[i]*s[i]%mod*c.c[i];
	}
	for(int i=1;i<=n-2;i++)
	{
		ans+=(long long)(n-1-i)*C(i+m-2,m-1)%mod*C(i+m-2,m-1);
		ans-=(long long)(n-1-i)*C(i+m-2,i)%mod*C(i+m-2,m);
	}
	for(int i=1;i<=m-2;i++)
	{
		ans+=(long long)(m-1-i)*C(i+n-2,n-1)%mod*C(i+n-2,n-1);
		ans-=(long long)(m-1-i)*C(i+n-2,i)%mod*C(i+n-2,n);
	}
	cout<<int((ans+2)%mod+mod)%mod<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 17ms
memory: 24096kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 12ms
memory: 24104kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 190ms
memory: 33532kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

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

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 18ms
memory: 24168kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 6ms
memory: 24104kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

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

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 16ms
memory: 24160kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

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

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

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

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 18ms
memory: 24352kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

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

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 16ms
memory: 24352kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 20ms
memory: 24572kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

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

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

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

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 18ms
memory: 24320kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 17ms
memory: 24280kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 15ms
memory: 24376kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 19ms
memory: 24544kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 18ms
memory: 24580kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 18ms
memory: 24280kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

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

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 192ms
memory: 33376kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 86ms
memory: 27472kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 77ms
memory: 27032kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 52ms
memory: 26180kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 186ms
memory: 32120kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 95ms
memory: 28240kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 90ms
memory: 27920kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 77ms
memory: 26948kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 82ms
memory: 27004kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 101ms
memory: 28744kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 190ms
memory: 32972kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 195ms
memory: 33392kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 195ms
memory: 33812kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 18ms
memory: 20292kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 31ms
memory: 21152kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 42ms
memory: 25924kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 8ms
memory: 24412kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed