QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#236284 | #7634. Cards | ucup-team870 | AC ✓ | 8817ms | 101092kb | C++14 | 4.0kb | 2023-11-03 19:50:50 | 2023-11-03 19:50:51 |
Judging History
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