QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#350437 | #8177. Sum is Integer | KNU_0_GB_RAM (Vladyslav Zavodnyk, Kostiantyn Lutsenko, Kostiantyn Savchuk)# | WA | 0ms | 3596kb | C++14 | 1.5kb | 2024-03-10 18:35:40 | 2024-03-10 18:35:40 |
Judging History
answer
#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
int inv(int x) {
return x < 2 ? x : mod - (mod / x) * 1ll * inv(mod % x) % mod;
}
vector<ll> get_pent(int n) {
vector<ll> penta(n + 1);
penta[0] = 1;
penta[1] = -1;
for(ll x = 0; x <= n; x++) {
ll a = (3*x*x+7*x+4) / 2;
ll b = a + 2*x + 3;
// cout << a << " " << b << endl;
if(a > n && b > n) break;
if(a <= n) penta[a] = x % 2 ? 1 : -1;
if(b <= n) penta[b] = (x+1) % 2 ? 1 : -1;
}
return penta;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
// vector<ll> dp(m); dp[0] = 1;
// for(int k = n; k >= 1; k--) {
// int X = inv(k) % mod;
// vector<ll> ndp(m);
// for(int i = m; i--;) {
// for(int t = 0; t < k && i - t >= 0; t++)
// ndp[i] = (ndp[i] + dp[i - t] * X) % mod;
// }
// dp = ndp;
// }
// ll fact = 1, v = 0;
// for(int i = 0; i < m; i++) v = (v + dp[i]) % mod;
// cout << v << endl;
vector<ll> dp(n + 1);dp[0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = n; j - i >= 0; j--)
dp[j] = (dp[j] - dp[j - i]) % mod;
}
for(int T = n; T--;) {
for(int i = 1; i <= n; i++) {
// assert(i < dp.size());
dp[i] += dp[i - 1];
}
}
int v = 0;
for(int i = 0; i < m; i++) v += dp[i];
cout << v << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3596kb
input:
4 1 6 1 3 1 2 1 2
output:
1
result:
wrong answer 1st words differ - expected: '2', found: '1'