QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308020 | #7875. Queue Sorting | confesser | WA | 129ms | 4796kb | C++17 | 1.6kb | 2024-01-19 13:32:44 | 2024-01-19 13:32:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using pi=pair<int,int>;
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define G(i,a,b) for(int i=(a);i>=(b);i--)
#define ms(a,b) memset(a,b,sizeof(a))
#define si(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
#define pb push_back
const int mod=998244353;
struct mint{
int x;
mint(int x=0):x(x){}
mint&operator+=(mint a){if((x+=a.x)>=mod)x-=mod;return *this;}
mint&operator-=(mint a){if((x-=a.x)<0)x+=mod;return *this;}
mint&operator*=(mint a){x=(ll)x*a.x%mod;return *this;}
friend mint operator+(mint a,mint b){return a+=b;}
friend mint operator-(mint a,mint b){return a-=b;}
friend mint operator*(mint a,mint b){return a*=b;}
mint pow(ll b=mod-2){
mint a=x,res=1;
for(;b;b>>=1,a*=a)if(b&1)res*=a;
return res;
}
};
vector<mint>fac,ifac,inv;
void initC(int n){
if(inv.empty())fac=ifac=inv=vector<mint>(2,1);
int m=inv.size(); ++n;
if(m>=n)return;
inv.resize(n),fac.resize(n),ifac.resize(n);
F(i,m,n-1){
inv[i]=inv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*inv[i];
}
}
mint C(int n,int m){
if(n<m||m<0)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
const int N=503;
int a[N],s[N];
mint dp[N][N];
int main(){
cin.tie(0)->ios::sync_with_stdio(0);
int n;
cin>>n;
F(i,1,n) cin>>a[i];
F(i,1,n) s[i]=s[i-1]+a[i];
dp[1][a[1]]=1;
F(i,1,n-1) F(j,1,s[i]){
F(x,0,a[i+1]-1) F(y,1,j){
dp[i+1][x+y]+=dp[i][j]*C(j-y+a[i+1]-x-1,j-y);
}
dp[i+1][a[i+1]+j]+=dp[i][j];
}
mint ans=0;
F(i,1,s[n]) ans+=dp[n][i];
cout<<ans.x;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4508kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 129ms
memory: 4796kb
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:
0
result:
wrong answer 1st numbers differ - expected: '507010274', found: '0'