QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#350437#8177. Sum is IntegerKNU_0_GB_RAM (Vladyslav Zavodnyk, Kostiantyn Lutsenko, Kostiantyn Savchuk)#WA 0ms3596kbC++141.5kb2024-03-10 18:35:402024-03-10 18:35:40

Judging History

This is the latest submission verdict.

  • [2024-03-10 18:35:40]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3596kb
  • [2024-03-10 18:35:40]
  • Submitted

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'