QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19505#1423. BinqingaodongTL 480ms5480kbC++205.1kb2022-02-02 10:55:142022-05-06 05:36:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 05:36:14]
  • 评测
  • 测评结果:TL
  • 用时:480ms
  • 内存:5480kb
  • [2022-02-02 10:55:14]
  • 提交

answer

#pragma GCC optimize("O3")
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <climits>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

const int M = 1e6 + 239;
const int MOD = 998244353;
const ll MOD2 = (ll)MOD * (ll)MOD;

int mul(long long a, int b) {
    return a * b % MOD;
}

int power(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = mul(ans, a);
        a = mul(a, a);
        b >>= 1;
    }
    return ans;
}

const int wp = power(3, 7 * 17); // w^(2^23) == 1

namespace fft {
    int k;
    vector<int> rev;
    vector<int> st;

    void fft(vector<int> &a) {
        for (int i = 0; i < k; i++)
            if (rev[i] < i)
                swap(a[rev[i]], a[i]);
        int w, wn, ai, aj;
        for (int s = 1, it = 0; s < k; s <<= 1, it++) {
            wn = st[it];
            for (int l = 0; l < k; l += s + s) {
                w = 1;
                for (int i = l, j = l + s; i < l + s; i++, j++) {
                    ai = a[i];
                    aj = 1LL * w * a[j] % MOD; // or st[((1 << 22) / s) * (i - l)]
                    a[i] = ai + aj;
                    if (a[i] >= MOD)
                        a[i] -= MOD;
                    a[j] = ai - aj;
                    if (a[j] < 0)
                        a[j] += MOD;
                    w = 1LL * w * wn % MOD;
                }
            }
        }
    }

    vector<int> mult(vector<int> a) {
        k = 1;
        while (k < (int)a.size() + (int)a.size() - 1)
            k <<= 1;
        if (st.size() != k)
        {
            st.clear();
            st.push_back(power(wp, ((1 << 22) / k)));
            for (int t = 1; t < k; t <<= 1)
                st.push_back(1LL * st.back() * st.back() % MOD);
            reverse(st.begin(), st.end());
            rev.clear();
            rev.resize(k);
            rev[0] = 0;
            for (int i = 1; i < k; i++)
            {
                if (i & 1)
                    rev[i] = rev[i - 1] + (k >> 1);
                else
                    rev[i] = rev[i >> 1] >> 1;
            }
        }
        a.resize(k);
        fft(a);
        //b.resize(k);
        //fft(b);
        vector<int> pr(k);
        for (int i = 0; i < k; i++)
            pr[i] = 1LL * a[i] * a[i] % MOD;
        fft(pr);
        reverse(pr.begin() + 1, pr.end());
        int inv_k = power(k, MOD - 2);
        for (int i = 0; i < k; i++)
            pr[i] = 1LL * pr[i] * inv_k % MOD;
        while (pr.back() == 0)
            pr.pop_back(); // can be removed
        return pr;
    }
}

/*int func(int l1, int r1, int l2, int r2, int n)
{
    if (n < l1 + l2)
        return 0;
    if (n >= r1 + r2 - 1)
        return 0;
    if (r1 - l1 == 1)
        return 1LL * dp[l1] * dp[n - l1] % MOD;
    if (r2 - l2 == 1)
        return 1LL * dp[n - l2] * dp[l2] % MOD;
    int ans = 0;
    int m1 = (l1 + r1) / 2;
    int m2 = (l2 + r2) / 2;
    ans += func(l1, m1, l2, m2, n);
    ans += func(m1, r1, l2, m2, n);
    if (ans >= MOD)
        ans -= MOD;
    ans += func(l1, m1, m2, r2, n);
    if (ans >= MOD)
        ans -= MOD;
    ans += func(m1, r1, m2, r2, n);
    if (ans >= MOD)
        ans -= MOD;
    return ans;
}*/

vector<int> dp;
vector<int> pr;

int n, k;

const int MG = 15000;

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    dp.resize(2);
    dp[0] = 0;
    dp[1] = 1;
    int g = 0;
    for (int i = 2; i <= n; i++)
    {
        if (i % MG == 0)
        {
            //cerr << i << "!\n";
            g = i;
            pr = fft::mult(dp);
        }
        dp.push_back(0);
        ll ci = 0;
        if (i < (int)pr.size())
            ci = pr[i];
        for (int j = g; j < i; j++)
        {
            ll add = (ll)dp[j] * dp[i - j];
            if (i - j < g)
            {
                add += add;
                if (add >= MOD2)
                    add -= MOD2;
            }
            ci += add;
            if (ci >= MOD2)
                ci -= MOD2;
        }
        ll sum = 0;
        for (int x = max(0, (i / 2) - k); x <= min(i - 1, (i / 2) + k); x++)
            if (abs(x - (i - x)) <= k)
            {
                sum += (ll)dp[x] * dp[i - x];
                if (sum >= MOD2)
                    sum -= MOD2;
            }
        dp[i] = ((ci % MOD) + (sum % MOD));
        if (dp[i] >= MOD)
            dp[i] -= MOD;
        if (dp[i] & 1)
            dp[i] += MOD;
        dp[i] /= 2;
    }
    cout << dp[n] << "\n";
    //cerr << TIME << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3616kb

input:

2 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

3 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 3ms
memory: 3632kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

4 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

4 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

4 2

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

6 2

output:

23

result:

ok 1 number(s): "23"

Test #8:

score: 0
Accepted
time: 3ms
memory: 3716kb

input:

7 42

output:

132

result:

ok 1 number(s): "132"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

10 1

output:

400

result:

ok 1 number(s): "400"

Test #10:

score: 0
Accepted
time: 3ms
memory: 3560kb

input:

13 4

output:

42003

result:

ok 1 number(s): "42003"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

239 17

output:

385818773

result:

ok 1 number(s): "385818773"

Test #12:

score: 0
Accepted
time: 480ms
memory: 5480kb

input:

50216 58

output:

744498776

result:

ok 1 number(s): "744498776"

Test #13:

score: -100
Time Limit Exceeded

input:

787788 78

output:


result: