QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#295885 | #4903. 细菌 | ucup-team1004 | 55 | 271ms | 14192kb | C++14 | 3.6kb | 2024-01-01 13:50:38 | 2024-01-01 13:50:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
out<<'[';
for(T x:a)out<<x<<',';
return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int mod=998244353;
ll qpow(ll x,ll y=mod-2,ll ans=1){
for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
return ans;
}
namespace Poly{
const int N=1<<18,g=3;
int lim,rev[N],A[N],B[N],pw[N];
void init(int n){
for(lim=1;lim<n;lim<<=1);
for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
}
void Init(){
int x=qpow(g,(mod-1)/N);
pw[N/2]=1;
for(int i=N/2+1;i<N;i++)pw[i]=1ll*pw[i-1]*x%mod;
for(int i=N/2-1;i;i--)pw[i]=pw[i<<1];
}
namespace Public{
using poly=vector<int>;
void NTT(int *f,int op){
static unsigned long long a[N];
for(int i=0;i<lim;i++)a[i]=f[rev[i]];
for(int len=1,x;len<lim;len<<=1){
for(int i=0;i<lim;i+=len<<1){
for(int j=0;j<len;j++){
x=a[i|j|len]*pw[len|j]%mod;
a[i|j|len]=a[i|j]+mod-x,a[i|j]+=x;
}
}
}
for(int i=0;i<lim;i++)f[i]=a[i]%mod;
if(op<0){
reverse(f+1,f+lim);
int x=qpow(lim);
for(int i=0;i<lim;i++)f[i]=1ll*f[i]*x%mod;
}
}
poly operator * (const poly &a,const poly &b){
int n=a.size(),m=b.size(),k=n+m-1;
init(k);
copy(a.begin(),a.end(),A),fill(A+n,A+lim,0);
copy(b.begin(),b.end(),B),fill(B+m,B+lim,0);
poly c(k);
NTT(A,1),NTT(B,1);
for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,-1);
for(int i=0;i<k;i++)c[i]=A[i];
return c;
}
poly& operator %= (poly &a,const int &b){
if(a.size()>b)a.resize(b);
return a;
}
poly operator % (const poly &a,const int &b){
poly c(a);
return c%=b;
}
}
}
using namespace Poly::Public;
const int N=1.2e5+10;
int d,n,m,k,a,b,c;
int fac[N],ifac[N];
void init(int n=d){
for(int i=fac[0]=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n]);
for(int i=n;i>=1;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m){
if(0>m||m>n)return 0;
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
const int B=501;
poly gen1(int n,int x){
static int f[2][B];
int now=1,las=0;
memset(f[now],0,sizeof f[now]);
f[now][x]=1;
poly g(d+1);
for(int i=0;i<=d;i++){
g[i]=accumulate(f[now]+1,f[now]+1+n,0ll)%mod;
swap(now,las);
for(int j=1;j<=n;j++)f[now][j]=(f[las][j-1]+f[las][j+1])%mod;
}
// debug(n,x,g);
return g;
}
poly gen2(int a,int b){
int n=a+b;
poly f(d+1);
vector<tuple<int,int,int,int>>s;
for(int l=-a,r=b,w=1;r>=-d;l-=n,r-=n,w=-w)s.push_back({l,r,w,0});
for(int l=-a,r=b,w=1;l+=n,r+=n,w=-w,l<=d;)s.push_back({l,r,w,0});
for(auto &[l,r,w,t]:s)t=l<=0&&0<=r;
f[0]=1;
for(int i=1;i<=d;i++){
for(auto &[l,r,w,t]:s){
t=t*2%mod;
if((r&1)^(i&1))(t+=C(i-1,(-r+i-1)/2))%=mod;
else (t+=mod-C(i-1,(-r+i)/2))%=mod;
if((l&1)^(i&1))(t+=C(i-1,(-l+i-1)/2))%=mod;
else (t+=mod-C(i-1,(-l+i)/2-1))%=mod;
// debug(i,l,r,w,t,(r&1)^(i&1),(l&1)^(i&1));
f[i]=(f[i]+t*w)%mod;
}
f[i]=(f[i]+mod)%mod;
}
// debug(a,b,f);
// exit(0);
return f;
}
poly gen(int n,int x){
auto f=n<B?gen1(n,x):gen2(x,n-x+1);
for(int i=0;i<f.size();i++)f[i]=1ll*f[i]*ifac[i]%mod;
return f;
}
int main(){
cin>>d>>n>>m>>k>>a>>b>>c;
Poly::Init(),init();
poly f=gen(n,a)*gen(m,b)%(d+1)*gen(k,c);
f.resize(d+1);
cout<<1ll*f[d]*fac[d]%mod<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 7716kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8532kb
input:
50 49 44 48 49 15 25
output:
544847893
result:
ok 1 number(s): "544847893"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 10
Accepted
time: 4ms
memory: 8180kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 4ms
memory: 7932kb
input:
5000 4994 4997 4994 4399 1826 1332
output:
65414465
result:
ok 1 number(s): "65414465"
Subtask #3:
score: 15
Accepted
Test #5:
score: 15
Accepted
time: 77ms
memory: 14076kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 271ms
memory: 14104kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 39ms
memory: 14144kb
input:
120000 119999 1 1 19896 1 1
output:
68846585
result:
ok 1 number(s): "68846585"
Subtask #4:
score: 10
Accepted
Test #8:
score: 10
Accepted
time: 37ms
memory: 14152kb
input:
119000 119991 119991 1 23819 52139 1
output:
944500934
result:
ok 1 number(s): "944500934"
Subtask #5:
score: 15
Accepted
Dependency #4:
100%
Accepted
Test #9:
score: 15
Accepted
time: 71ms
memory: 14112kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 0
Accepted
time: 72ms
memory: 14096kb
input:
120000 13997 13997 1 9768 6131 1
output:
151873213
result:
ok 1 number(s): "151873213"
Subtask #6:
score: 0
Wrong Answer
Dependency #3:
100%
Accepted
Dependency #5:
100%
Accepted
Test #11:
score: 35
Accepted
time: 109ms
memory: 14048kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 0
Accepted
time: 125ms
memory: 14124kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: -35
Wrong Answer
time: 153ms
memory: 14192kb
input:
120000 491 495 1 430 25 1
output:
103995581
result:
wrong answer 1st numbers differ - expected: '272929924', found: '103995581'
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
0%