QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234233 | #7632. Balanced Arrays | Geospiza# | WA | 400ms | 43488kb | C++20 | 4.2kb | 2023-11-01 15:01:41 | 2023-11-01 15:01:41 |
Judging History
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'