QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234139 | #7632. Balanced Arrays | Geospiza# | TL | 19ms | 36076kb | C++20 | 2.5kb | 2023-11-01 14:25:39 | 2023-11-01 14:25:39 |
Judging History
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