QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234139#7632. Balanced ArraysGeospiza#TL 19ms36076kbC++202.5kb2023-11-01 14:25:392023-11-01 14:25:39

Judging History

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

  • [2023-11-01 14:25:39]
  • 评测
  • 测评结果:TL
  • 用时:19ms
  • 内存:36076kb
  • [2023-11-01 14:25:39]
  • 提交

answer

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define Ma 2000005
#define G 3
#define pb push_back
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=sum*p%mod;
        p=p*p%mod;
        x>>=1;
    }
    return sum;
}

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

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

ll rev[Ma];

void change(vector <ll> &x,ll len){
    for (ll i=0;i<len;i++){
        rev[i]=rev[i>>1]>>1;
        if (i&1)
            rev[i]|=len>>1;
    }
    for (ll i=0;i<len;i++)
        if (rev[i]<i)
            swap(x[i],x[rev[i]]);
    return;
}

void NTT(vector <ll> &x,ll lim,ll on){
    change(x,lim);
    for (ll h=2;h<=lim;h<<=1){
        ll gn=po(G,(mod-1)/h);
        for (ll j=0;j<lim;j+=h){
            ll g=1;
            for (ll k=j;k<j+h/2;k++,g=g*gn%mod){
                ll tmp=x[k+h/2]*g%mod;
                x[k+h/2]=(x[k]-tmp+mod)%mod;
                x[k]=(x[k]+tmp)%mod;
            }
        }
    }
    if (on==-1){
        reverse(x.begin()+1,x.end());
        ll inv=po(lim);
        for (ll i=0;i<lim;i++) x[i]=x[i]*inv%mod;
    }
    return;
}


vector <ll> M(vector <ll> x,vector <ll> y,ll L){
    ll len=x.size()+y.size()-1,lim=1;
    while (lim<=len) lim<<=1;
    x.resize(lim),y.resize(lim);
    NTT(x,lim,1),NTT(y,lim,1);
    for (ll i=0;i<lim;i++)
        x[i]=x[i]*y[i]%mod;
    NTT(x,lim,-1);
    len=min(len,L);
    x.resize(len);
    return x;
}

ll n,m;

vector <ll> po(vector <ll> p,ll x)
{
    vector <ll> sum;
    sum.pb(1);
    while (x)
    {
        if (x&1) sum=M(sum,p,m+1);
        p=M(p,p,m+1);
        x>>=1;
    }
    return sum;

}


void sol()
{
    cin>>n>>m;
    vector <ll> s;
    for (ll i=0;i<=m;i++)
        s.pb(1);
    s=po(s,n);
    for (ll i=1;i<=m;i++)
        s[i]=(s[i]+s[i-1])%mod;
    ll ans=0;
    for (ll i=0;i<n&&i<=m;i++)
        ans=(ans+C(i,n-1)*s[m-i])%mod;
    printf("%lld\n",ans);
    return;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 19ms
memory: 36076kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Time Limit Exceeded

input:

500000 500000

output:


result: