QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#278292 | #7875. Queue Sorting | lifan | WA | 0ms | 11904kb | C++14 | 1.2kb | 2023-12-07 14:38:40 | 2023-12-07 14:38:40 |
Judging History
answer
//
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 510,mod = 998244353;
void add(ll& x,ll y){x=(x+y)%mod;}
ll addv(ll x,ll y){return (x+y)%mod;}
//
ll n,a[MAXN],dp[MAXN][MAXN],s;
ll C[MAXN*2][MAXN*2];
int main(){
rep(i,0,1000){
C[i][0]=1;
rep(j,1,i)C[i][j]=addv(C[i-1][j-1],C[i-1][j]);
}
cin>>n;
rep(i,1,n)cin>>a[i];
s=1;
while(s<=n && !a[s])s++;
if(s==n+1)return (cout<<"1\n"),0;
ll sum=a[s];
dp[s][0]=1;
rep(i,s+1,n){
if(!a[i]){
memcpy(dp[i],dp[i-1],sizeof dp[i]);
continue;
}
rep(j,0,sum)if(dp[i-1][j]){
ll val=dp[i-1][j];
add(dp[i][j],val);
rep(k,0,a[i]-1){ //枚举最后一格放的个数
ll r=a[i]-k;
rep(p,j,sum-1){
ll x=p-j+1,w=C[x+r-2][r-1];
add(dp[i][p+r],val*w);
}
}
}
sum+=a[i];
}
ll ans=0;
rep(i,0,sum)add(ans,dp[n][i]);
cout<<ans+1<<endl;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 11904kb
input:
4 1 1 1 1
output:
15
result:
wrong answer 1st numbers differ - expected: '14', found: '15'