QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563303#7875. Queue SortingBreakPlusWA 21ms7144kbC++141.5kb2024-09-14 09:35:182024-09-14 09:35:19

Judging History

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

  • [2024-09-14 09:35:19]
  • 评测
  • 测评结果:WA
  • 用时:21ms
  • 内存:7144kb
  • [2024-09-14 09:35:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define pb emplace_back
#define fi first
#define se second
#define mkp make_pair
const ll mod = 998244353;
inline ll read() { ll x; scanf("%lld",&x); return x; }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}

ll n,a[505],f[505][505];
void init(){ }

inline void addmod(ll &a, ll b){
	a += b; if(a >= mod) a -= mod;
}
inline void Addmod(ll &a, ll b){
	a = (a + b) % mod;
}
ll C[505][505];
void procedure(){
	n=read();	
	C[0][0]=1;
	for(ll i=1;i<=n;i++){
		C[i][0]=1;
		for(ll j=1;j<=i;j++){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	for(ll i=1;i<=n;i++) a[i]=read();
	f[0][0]=1;
	for(ll i=0;i<n;i++){
		for(ll j=0;j<=n;j++){
			if(!f[i][j]) continue;
			// cout<<"here "<<i<<", "<<j<<" has "<<f[i][j]<<endl;
			addmod(f[i+1][j+a[i+1]], f[i][j]);
			// cout<<"trans to "<<i+1<<" "<<j+a[i]<<endl;
			for(ll k=0;k<j;k++){
				for(ll l=0;l<a[i+1];l++){
					if(l) Addmod(f[i+1][j-k+l], f[i][j] * C[l-1+j-k][j-k]);
					else addmod(f[i+1][j-k+l], f[i][j]);
				}
			}
		}
	}
	ll ans=0;
	for(ll i=0;i<=n;i++) addmod(ans, f[n][i]);
	printf("%lld\n", ans);
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=1; init();
	// T=read();
	while(T--) procedure();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5964kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Wrong Answer
time: 21ms
memory: 7144kb

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:

524016798

result:

wrong answer 1st numbers differ - expected: '507010274', found: '524016798'