QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#275813 | #7875. Queue Sorting | pengpeng_fudan | WA | 41ms | 4628kb | C++14 | 1.6kb | 2023-12-05 08:31:51 | 2023-12-05 08:31:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
const ll mod=998244353;
ll dp[510][510];
int n;ll a[510];
ll pw[1010],inv[1010];
ll qpow(ll a,ll b,ll mod){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
void intt(){
pw[0]=1;
for(int i=1;i<=1000;i++) pw[i]=pw[i-1]*i%mod;
inv[1000]=qpow(pw[1000],mod-2,mod);
for(int i=999;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
inv[0]=1;
}
ll get(int x,int y){
return pw[x]*inv[y]%mod*inv[x-y]%mod;
}
ll pz[5010];
void solve() {
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
pz[n+1]=1;
ll sm=0,seg=1;
for(int i=n;i>=1;i--){
sm+=a[i];seg=seg*inv[a[i]]%mod;
pz[i]=pw[sm]*seg%mod;
}
ll ans=0;
dp[0][0]=1;int pre=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=pre-1;j++){
ll t=dp[i-1][j]*(get(pre+a[i],pre)-get(pre+a[i]-j,pre-j))%mod*pz[i+1]%mod*get(sm,pre+a[i])%mod;
ans=((ans+t)%mod+mod)%mod;
}
for(int j=0;j<=pre;j++){
dp[i][j]=dp[i-1][j];
ll t=0;
for(int k=0;k<j;k++){
t=(t+dp[i-1][k]*get(a[i]+pre-j,pre-j+1)%mod)%mod;
//if(i==4&&j==2) cout<<k<<' '<<t<<'\n';
}
dp[i][j]=(dp[i][j]+t)%mod;
}
pre+=a[i];
}
cout<<((pz[1]-ans)%mod+mod)%mod;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int _ = 1;
intt();
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3484kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 41ms
memory: 4628kb
input:
300 0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...
output:
494615542
result:
wrong answer 1st numbers differ - expected: '507010274', found: '494615542'