QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#278292#7875. Queue SortinglifanWA 0ms11904kbC++141.2kb2023-12-07 14:38:402023-12-07 14:38:40

Judging History

你现在查看的是最新测评结果

  • [2023-12-07 14:38:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11904kb
  • [2023-12-07 14:38:40]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'