QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234233#7632. Balanced ArraysGeospiza#WA 400ms43488kbC++204.2kb2023-11-01 15:01:412023-11-01 15:01:41

Judging History

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

  • [2023-11-01 15:01:41]
  • 评测
  • 测评结果:WA
  • 用时:400ms
  • 内存:43488kb
  • [2023-11-01 15:01:41]
  • 提交

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<<21)
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;
    poly s(n+1);
    ll f=1;
    for (ll i=0;i<=n;i++)
    {
        s[i]=(C(i,n)*f+mod)%mod;
        f=-f;
    }
    poly g=s.inv(m+1);
    for (ll i=1;i<=m;i++)
        g[i]=(g[i]+g[i-1])%mod;
    ll ans=0;
    for (ll i=0;i<n&&i<=m;i++)
        ans=(ans+1ll*C(i,n-1)*g[m-i]%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;
}
/*500000 500000*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Wrong Answer
time: 400ms
memory: 43488kb

input:

500000 500000

output:

197056887

result:

wrong answer 1st numbers differ - expected: '984531374', found: '197056887'