QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308020#7875. Queue SortingconfesserWA 129ms4796kbC++171.6kb2024-01-19 13:32:442024-01-19 13:32:44

Judging History

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

  • [2024-01-19 13:32:44]
  • 评测
  • 测评结果:WA
  • 用时:129ms
  • 内存:4796kb
  • [2024-01-19 13:32:44]
  • 提交

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'