QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#273964#7875. Queue Sortingucup-team2000#RE 0ms0kbC++202.5kb2023-12-03 06:59:562023-12-03 06:59:57

Judging History

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

  • [2023-12-03 06:59:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-12-03 06:59:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lep(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,b,a) for (int i = (b); i >= (a); i--)
const int inf = 1e18;

const int maxn = 1003;
const int mod = 998244353;

int reduce(int a) {
	return (a %= mod) < 0 ? a + mod : a;
}

int prod(int a, int b) {
	return reduce(reduce(a) * reduce(b));
}

int add(int a, int b) {
	return reduce(reduce(a)+reduce(b));
}

int modpow(int a, int pw) {
	if (a == 0) return 0;
	if (pw == 0) return 1;
	if (pw&1) return prod(modpow(a,pw-1), a);
	int res = modpow(a, pw/2);
	return prod(res, res);
}

int inv(int a) {
	return modpow(a, mod-2);
}

int dp1[maxn][maxn], dp2[maxn][maxn];
int fact[2*maxn];
int ifact[2*maxn];

int ncr(int n, int k) {
	// cout << "n: "<< n << ", k: " << k << endl;
	assert(k < maxn);
	if (k > n or n < 0) return 0;
	return prod(fact[n], prod(ifact[k], ifact[n-k]));
}

vector<int> prefs[maxn];

int solve2(int i, int j, int S) {
	int idx1 = max(0LL, i-S);
	int idx2 = min(j-1,S+1);
	int ans = prefs[S][idx2];
	if (idx1 == 0) ans = add(ans, -prefs[S][0]);
	return ans;
}

int solve1(int i, int j, int nxt) {
	int target_sum = i+j-nxt;
	cout << "nxt: " << nxt << "\n";
	if (target_sum == i+j-1) return 1;
	int ans = solve2(i,j,target_sum);
	cout << "i: " << i << ", j: " << j << ", nxt: " << nxt << "\n";
	if (ans != 0) {
		cout << "hi\n";
	}
	return ans;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n;
	cin >> n;
	fact[0] = 1;
	lep(i,1,2*maxn-1) fact[i] = prod(i, fact[i-1]);
	lep(i,0,2*maxn-1) ifact[i] = inv(fact[i]);
	lep(i,1,maxn-1) lep(j,0,maxn-1) dp2[i][j] = ncr(i+j-1,i);
	rep(i,maxn-1,1) lep(j,0,maxn-1) if (i+j < maxn) prefs[i+j].pb(prefs[i+j].empty()?dp2[i][j]:add(prefs[i+j].back(),dp2[i][j]));
	vector<int> a(n+1);
	vector<int> elts;
	lep(i,1,n) {
		cin >> a[i];
	}
	vector<int> b = {0};
	lep(i,1,n) {
		if (a[i] > 0) b.pb(a[i]);
	}
	a = b;
	n = a.size()-1;
	dp1[1][a[1]] = 1;
	cout << "a:\n";
	lep(i,1,n) {
		cout << a[i] << " ";
	}
	cout << "\n";
	lep(i,1,n-1) {
		lep(j,1,maxn/2) {
			lep(nxt,1,a[i+1]+a[i]) {
				dp1[i+1][nxt] = add(dp1[i+1][nxt], prod(dp1[i][j], solve1(j,a[i+1],nxt)));
			}
		}
	}
	lep(i,1,n) {
		lep(j,1,i) {
			cout << dp1[i][j] << " ";
		}
		cout << "\n";
	}
	int ans = 0;
	lep(i,0,maxn-1) {
		ans = add(ans, dp1[n][i]);
	}
	cout << ans << "\n";

	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

4
1 1 1 1

output:


result: