QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89245 | #1839. Joke | eyiigjkn | WA | 3ms | 3612kb | C++14 | 2.1kb | 2023-03-19 13:36:01 | 2023-03-19 13:36:05 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Poly=vector<int>;
constexpr int mod=988244353;
int a[110],b[110],p[110],c1[110],c2[110],fac[110],inv[110],f[110],g[110][110],y[110];
inline void add(int &x,const auto &y){x=(x+y)%mod;}
Poly operator+(const Poly &F,const Poly &G)
{
int n=F.size(),m=G.size();
Poly H(max(n,m));
copy(F.begin(),F.end(),H.begin());
for(int i=0;i<m;i++) add(H[i],G[i]);
return H;
}
Poly operator*(const Poly &F,const int &x)
{
Poly G=F;
for(int &i:G) i=(ll)i*x%mod;
return G;
}
Poly operator*(const Poly &F,const Poly &G)
{
int n=F.size(),m=G.size();
Poly H(n+m-1);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
add(H[i+j],(ll)F[i]*G[j]);
return H;
}
Poly div(Poly F,const int &a)
{
int n=F.size();
Poly G(n-1);
for(int i=n-1;i;i--) G[i-1]=F[i],add(F[i-1],(ll)a*F[i]);
return G;
}
Poly Langrange(int n)
{
Poly mul={1},F;
for(int i=0;i<=n;i++) mul=mul*Poly{mod-i,1};
for(int i=0;i<=n;i++)
{
Poly G=div(mul,i)*y[i];
for(int j=0;j<i;j++) G=G*inv[i-j];
for(int j=n;j>i;j--) G=G*(mod-inv[j-i]);
F=F+G;
}
return F;
}
int main()
{
int n,ans=0;
cin>>n;
fac[0]=fac[1]=inv[1]=1;
for(int i=2;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
for(int i=2;i<=n;i++) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) p[a[i]]=b[i];
p[n+1]=n+1;
fill(c1+1,c1+n+1,1);
fill(c2+1,c2+n+1,1);
for(int i=1;i<=n;i++)
if(p[i]) c1[i]=c2[p[i]]=0;
partial_sum(c1+1,c1+n+2,c1+1);
partial_sum(c2+1,c2+n+2,c2+1);
for(int x=0;x<=n;x++)
{
for(int i=0;i<=n;i++) g[i][0]=g[0][i]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=(g[i-1][j]+g[i][j-1]+(ll)(mod+x-1)*g[i-1][j-1])%mod;
f[0]=1;
for(int i=1;i<=n+1;i++)
{
if(!p[i]) continue;
for(int j=0;j<i;j++)
if(p[j]<p[i]) add(f[i],(ll)f[j]*g[c1[i]-c1[j]][c2[p[i]]-c2[p[j]]]);
}
y[x]=f[n+1];
memset(f,0,sizeof(int)*(n+2));
}
Poly F=Langrange(n);
for(int i=0,sz=F.size();i<sz && i<=c1[n];i++) add(ans,(ll)F[i]*fac[c1[n]-i]);
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3396kb
input:
2 1 2 2 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
4 4 3 2 1 4 3 2 1
output:
16
result:
ok 1 number(s): "16"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
5 1 2 3 4 5 0 0 0 0 0
output:
1546
result:
ok 1 number(s): "1546"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
6 1 6 2 5 3 4 0 1 0 2 0 3
output:
52
result:
ok 1 number(s): "52"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3520kb
input:
10 8 2 10 3 4 6 1 7 9 5 0 0 0 0 0 0 0 0 0 0
output:
234662231
result:
ok 1 number(s): "234662231"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
10 5 8 4 9 6 1 2 7 3 10 8 3 0 5 0 9 0 0 6 0
output:
5294
result:
ok 1 number(s): "5294"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
10 4 2 6 9 5 3 8 1 10 7 0 9 8 0 7 3 4 2 1 10
output:
166
result:
ok 1 number(s): "166"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3516kb
input:
10 8 2 7 1 5 9 3 4 10 6 7 0 2 9 5 1 8 4 3 6
output:
26
result:
ok 1 number(s): "26"
Test #9:
score: 0
Accepted
time: 3ms
memory: 3516kb
input:
10 10 1 6 7 9 8 4 3 5 2 2 5 1 3 9 10 4 8 6 7
output:
47
result:
ok 1 number(s): "47"
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 3520kb
input:
50 41 15 17 1 5 31 7 38 30 39 43 35 2 26 20 42 48 25 19 32 50 4 8 10 44 12 9 18 13 36 28 6 27 23 40 24 3 14 29 11 49 47 45 46 34 21 37 16 22 33 0 0 0 0 0 0 0 0 0 33 34 0 0 0 0 0 0 0 0 0 0 2 0 0 0 20 0 0 28 0 0 0 9 0 0 0 48 0 0 0 50 0 0 0 0 5 0 0 32 0
output:
691900132
result:
wrong answer 1st numbers differ - expected: '976189245', found: '691900132'