QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#273964 | #7875. Queue Sorting | ucup-team2000# | RE | 0ms | 0kb | C++20 | 2.5kb | 2023-12-03 06:59:56 | 2023-12-03 06:59:57 |
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