QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236284#7634. Cardsucup-team870AC ✓8817ms101092kbC++144.0kb2023-11-03 19:50:502023-11-03 19:50:51

Judging History

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

  • [2023-11-03 19:50:51]
  • 评测
  • 测评结果:AC
  • 用时:8817ms
  • 内存:101092kb
  • [2023-11-03 19:50:50]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
#define vi vector<int>
typedef long long ll;
typedef pair<int,int> P;
const int mod=998244353,N=2e5+5,G=3;
ll qp(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod; y>>=1;
    } return res;
}
const int Gi=qp(G,mod-2);
typedef vi poly;
int limit=1,L=0, r[N*4];
inline int qm(int x){x-=mod; x-=mod*(x>>31); return x;}
void NTT(poly &A,int tp){
    A.resize(limit);
    for(int i=0;i<limit;++i){
        if(i<r[i])swap(A[r[i]],A[i]);
    }
    for(int mid=1;mid<limit;mid<<=1){
        ll wn=qp(tp==1?G:Gi, (mod-1)/(mid<<1));
        for(int j=0;j<limit;j+=(mid<<1)){
            ll w=1;
            for(int k=0;k<mid;k++,w=(w*wn)%mod){
                int x=A[j+k], y=w*A[j+k+mid]%mod;
                A[j+k]=qm(x+y); A[j+k+mid]=qm(x-y+mod);
            }
        }
    }
}
void poly_mul_init(poly &a,poly &b){
    limit=1; L=0;
    int N=a.size()-1,M=b.size()-1;
    while(limit<=N+M)limit<<=1,++L;
    for(int i=0;i<limit;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
}
poly poly_mul(poly a,poly b){
    int n=a.size()+b.size()-1;
    poly_mul_init(a,b);
    NTT(a,1); NTT(b,1);
    rep(i,0,limit-1)a[i]=1ll*a[i]*b[i]%mod;
    NTT(a,-1);
    ll inv=qp(limit,mod-2);
    rep(i,0,limit-1)a[i]=a[i]*inv%mod;
    a.resize(n); return a;
}
poly f_1,f_2,g_1,g0,g1,g_n1,g_n2;
void wk(poly&h,poly &f,poly &g,int l,int r){
    int mid=l+r>>1;
    poly b(r-l+1);
    rep(i,0,r-l)b[i]=g[i];
    poly a(mid-l+1); rep(i,0,mid-l)a[i]=f[i+l];
    poly res=poly_mul(a,b);
    rep(i,mid+1,r)h[i]=(h[i]+res[i-l])%mod;
}
void cdqfft(int l,int r){
    if(l==r){
        f_1[l]=(g_n1[l]-f_1[l]+mod)%mod;
        f_2[l]=(g_n2[l]-f_2[l]+mod)%mod;
        return;
    }
    int mid=l+r>>1;
    cdqfft(l,mid);
    wk(f_1,f_1,g0,l,r);
    wk(f_1,f_2,g1,l,r);
    wk(f_2,f_1,g_1,l,r);
    wk(f_2,f_2,g0,l,r);
    cdqfft(mid+1,r);
}
int p[5];
poly qp(poly x,int y){
    poly res={1};
    while(y){
        if(y&1)res=poly_mul(res,x);
        x=poly_mul(x,x); y>>=1;
    } return res;
}
int dp[N];
vi Q[N];
const int B=700;
void pre(int n){
    int up=2*n+3;
    poly q; rep(i,0,4)q.push_back(p[i]);
    poly pw=qp(q,B); if(pw.size()>up)pw.resize(up);
    for(int l=1;l<=n;l+=B){
        Q[l]=q;
        q=poly_mul(q,pw); if(q.size()>up)q.resize(up);
    }
    // cerr<<clock()<<endl;
}
poly cal(int n,int v){
    // const int B=max((int)sqrt(n*log(n)),1);
    poly res(n+1);
    // rep(i,1,n){
    //     int x=i*2+v;
    //     res[i]=x<0?0:(x>=q.size()?0:q[x]);
    //     q=poly_mul(q,pw);
    // }
    // return res;
    auto ask=[&](int i){
        i=2*i+v;
        return i<0?0:dp[i];
    };
    for(int l=1;l<=n;l+=B){
        auto &q=Q[l];
        int r=min(n,l+B-1);
        // cout<<l<<' '<<r<<endl;
        int L=max(0,v+2*l-4*B),R=v+2*r;
        rep(i,L,R){
            dp[i]=i>=q.size()?0:q[i];
        }
        rep(i,l,r){
            res[i]=ask(i);
            L=max(0,R-4*(r-i)-5);
            per(j,R,L){
                int v=0,jj=min(4,j);
                rep(k,0,jj){
                    v=(v+1ll*dp[j-k]*p[k])%mod;
                }
                dp[j]=v;
            }
        }
    }
    // cout<<"ok"<<endl;
    return res;
}
int main() {
    // IOS
    int v,n; cin>>v>>n;
    if(n==0){
        cout<<1; return 0;
    }
    int sum=0;
    rep(i,0,4)cin>>p[i],sum+=p[i]; sum=qp(sum,mod-2);
    rep(i,0,4)p[i]=1ll*p[i]*sum%mod;
    pre(n);
    g_1=cal(n,-1); g0=cal(n,0); g1=cal(n,1); 
    g_n1=cal(n,-v-1); g_n2=cal(n,-v-2);
    f_1.resize(n+1); f_2.resize(n+1);
    cdqfft(1,n);
    int ans=1;
    rep(i,1,n){
        ans=((ans-f_1[i]-f_2[i])%mod+mod)%mod;
    }
    cout<<ans<<'\n';
    return 0;
}
/*
1 1
1 1 1 1 1

100000 100000
1 1 1 1 1
971297801
*/

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 9360kb

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 8783ms
memory: 101092kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 8786ms
memory: 99912kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 8788ms
memory: 100116kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

score: 0
Accepted
time: 2ms
memory: 9168kb

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 3753ms
memory: 33148kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

score: 0
Accepted
time: 0ms
memory: 11392kb

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 8807ms
memory: 100968kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 8817ms
memory: 100696kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 8791ms
memory: 99648kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 8812ms
memory: 99472kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 8792ms
memory: 99696kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 8775ms
memory: 99736kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

score: 0
Accepted
time: 2ms
memory: 10280kb

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 452ms
memory: 10744kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 462ms
memory: 12124kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 383ms
memory: 11632kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed