QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235503#7632. Balanced ArraysGeospizaAC ✓39ms35832kbC++144.1kb2023-11-02 20:29:322023-11-02 20:29:32

Judging History

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

  • [2023-11-02 20:29:32]
  • 评测
  • 测评结果:AC
  • 用时:39ms
  • 内存:35832kb
  • [2023-11-02 20:29:32]
  • 提交

answer

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll int
#define mod 998244353
#define Ma 2000005
#define G 3
#define pb push_back
#define L (1<<22)
using namespace std;

ll mul[Ma],pre[Ma];
ll po(ll p,ll x=mod-2)
{
    ll sum=1;
    while (x)
    {
        if (x&1) sum=1ll*sum*p%mod;
        p=1ll*p*p%mod;
        x>>=1;
    }
    return sum;
}

void pri()
{
    mul[0]=pre[0]=1;
    for (ll i=1;i<Ma;i++)
        mul[i]=1ll*mul[i-1]*i%mod;
    pre[Ma-1]=po(mul[Ma-1]);
    for (ll i=Ma-2;i>=0;i--)
        pre[i]=1ll*pre[i+1]*(i+1)%mod;
    return;
}

ll C(ll x,ll y)
{
    if (x<0||y<0||x>y) return 0;
    return 1ll*mul[y]*pre[x]%mod*pre[y-x]%mod;
}

inline void inc(int &x,int y){
    x+=y;
    if (x>=mod) x-=mod;
    if (x<0) x+=mod;
}

inline void dec(int &x,int y){
    x-=y;
    if (x<0) x+=mod;
    if (x>=mod) x-=mod;
}

int fpow(int x,int k=mod-2){
    int r=1;
    for (;k;k>>=1,x=1ll*x*x%mod){
        if (k&1) r=1ll*r*x%mod;
    }
    return r;
}
int w[L],_=[]{
    w[L/2]=1;
    for (ll i=L/2+1,x=fpow(G,(mod-1)/L);i<L;i++)
        w[i]=1ll*w[i-1]*x%mod;
    for (ll i=L/2-1;i>=0;i--)
        w[i]=w[i<<1];
    return 0;
}();

void dft(ll *a,ll n){
    for (ll k=n>>1;k;k>>=1){
        for (ll i=0;i<n;i+=k<<1){
            for (ll j=0;j<k;j++){
                ll &x=a[i+j],y=a[i+j+k];
                a[i+j+k]=1ll*(x-y+mod)*w[k+j]%mod;
                inc(x,y);
            }
        }
    }
}

void idft(ll *a,ll n){
    for (ll k=1;k<n;k<<=1){
        for (ll i=0;i<n;i+=k<<1){
            for (ll j=0;j<k;j++){
                int x=a[i+j],y=1ll*a[i+j+k]*w[k+j]%mod;
                a[i+j+k]=x-y<0?x-y+mod:x-y;
                inc(a[i+j],y);
            }
        }
    }
    for (ll i=0,inv=mod-(mod-1)/n;i<n;i++){
        a[i]=1ll*a[i]*inv%mod;
    }
    std::reverse(a+1,a+n);
}

inline int norm(int n) {return 1<<std::__lg(n*2-1);}

struct poly : public std::vector <ll>
{
    #define T (*this)
    using std::vector <ll> ::vector;

    void append(const poly &r){
        insert(end(),r.begin(),r.end());
    }

    ll len() const{ return size();}

    poly &operator ^=(const poly &r)
    {
        if (r.len()<len()) resize(r.len());
        for (ll i=0;i<len();i++)
            T[i]=1ll*T[i]*r[i]%mod;
        return T;
    }

    poly &operator *=(int r)
    {
        for (ll &x:T) x=1ll*x*r%mod;
        return T;
    }

    poly operator -() const{
        poly r(T);
        for (auto &x:r) x=x?mod-x:0;
        return r;
    }

    poly operator *(int r) const {return poly(T)*=r;}

    poly operator >>(int r) const{
        return r>=len()?poly():poly(begin()+r,end());
    }


    poly pre(int k) const{
        return k<len()?poly(begin(),begin()+k):T;
    }

    friend void dft(poly &a){(dft(a.data(),a.len()));}

    friend void idft(poly &a){(idft(a.data(),a.len()));}

    friend poly conv(const poly &a,const poly &b,int n)
    {
        poly p(a),q;
        p.resize(n),dft(p);
        p^=&a==&b?p:(q=b,q.resize(n),dft(q),q);
        idft(p);
        return p;
    }

    friend poly operator*(const poly &a,const poly &b){
        ll len=a.len()+b.len()-1;
        if (a.len()<=16||b.len()<=16){
            poly c(len);
            for (ll i=0;i<a.len();i++)
                for (ll j=0;j<b.len();j++)
                    c[i+j]=(c[i+j]+1ll*a[i]*b[j]%mod)%mod;
            return c;
        }
        return conv(a,b,norm(len)).pre(len);
    }


    poly inv(ll m)const{
        poly x={fpow(T[0])};
        for (ll k=1;k<m;k<<=1){
            x.append(-((conv(pre(k*2),x,k*2)>>k)*x).pre(k));
        }
        return x.pre(m);
    }
};

ll n,m;
void sol()
{
    cin>>n>>m;
    ll ans=0;
    ll f=1;
    for (ll i=0;i<=n&&i<=m;i++)
    {
    	ans=(ans+1ll*f*C(i,n)*C(n,m+n-i)%mod*C(n,m+n-i+1)%mod)%mod;
    	f=-f;
	}
	ans=1ll*ans*po(n+1)%mod;
	ans=(ans+mod)%mod;
	printf("%d\n",ans);
    return;
}

int	main(){
    ios::sync_with_stdio(0); cin.tie(0);
    pri();
    int tt=1;
   while (tt--)
        sol();
    return 0;
}
/*100 500000*/


这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 30ms
memory: 35572kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 39ms
memory: 35544kb

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

score: 0
Accepted
time: 26ms
memory: 35592kb

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

score: 0
Accepted
time: 30ms
memory: 35600kb

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

score: 0
Accepted
time: 29ms
memory: 35832kb

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 35ms
memory: 35720kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 35ms
memory: 35588kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

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

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 38ms
memory: 35528kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 35ms
memory: 35560kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

score: 0
Accepted
time: 35ms
memory: 35804kb

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 35ms
memory: 35568kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 34ms
memory: 35600kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 30ms
memory: 35596kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

score: 0
Accepted
time: 34ms
memory: 35604kb

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 34ms
memory: 35604kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 22ms
memory: 35528kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 36ms
memory: 35544kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

score: 0
Accepted
time: 30ms
memory: 35572kb

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

score: 0
Accepted
time: 26ms
memory: 35476kb

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

score: 0
Accepted
time: 34ms
memory: 35596kb

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

score: 0
Accepted
time: 34ms
memory: 35720kb

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

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

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

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

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

score: 0
Accepted
time: 28ms
memory: 35596kb

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

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

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 26ms
memory: 35608kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

score: 0
Accepted
time: 36ms
memory: 35604kb

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

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

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

score: 0
Accepted
time: 27ms
memory: 35580kb

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed