QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#127577#6325. Peaceful ResultsEnergy_is_not_overRE 123ms28848kbC++177.2kb2023-07-19 19:59:112023-07-19 19:59:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 19:59:14]
  • 评测
  • 测评结果:RE
  • 用时:123ms
  • 内存:28848kb
  • [2023-07-19 19:59:11]
  • 提交

answer

/**
 *  created: 17/07/2023, 20:21:09
**/

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

const int max_n = 1500111, mod = 998244353;

template<int mod>
struct NTT {
    static constexpr int max_lev = __builtin_ctz(mod - 1);

    int prod[2][max_lev - 1];

    NTT() {
        int root = (mod == 998244353) ? 31 : find_root();
        int rroot = inv(root);
        vector<vector<int>> roots(2, vector<int>(max_lev - 1));
        roots[0][max_lev - 2] = root;
        roots[1][max_lev - 2] = rroot;
        for (int tp = 0; tp < 2; ++tp) {
            for (int i = max_lev - 3; i >= 0; --i) {
                roots[tp][i] = mul(roots[tp][i + 1], roots[tp][i + 1]);
            }
        }
        for (int tp = 0; tp < 2; ++tp) {
            int cur = 1;
            for (int i = 0; i < max_lev - 1; ++i) {
                prod[tp][i] = mul(cur, roots[tp][i]);
                cur = mul(cur, roots[tp ^ 1][i]);
            }
        }
    }

    template<bool inverse>
    void fft(int *a, int lg) const {
        const int n = 1 << lg;
        int pos = max_lev - 1;
        for (int it = 0; it < lg; ++it) {
            const int h = inverse ? lg - 1 - it : it;
            const int shift = (1 << (lg - h - 1));
            int coef = 1;
            for (int start = 0; start < (1 << h); ++start) {
                for (int i = start << (lg - h); i < (start << (lg - h)) + shift; ++i) {
                    if (!inverse) {
                        const int y = mul(a[i + shift], coef);
                        a[i + shift] = a[i];
                        inc(a[i], y);
                        dec(a[i + shift], y);
                    } else {
                        const int y = mul(a[i] + mod - a[i + shift], coef);
                        inc(a[i], a[i + shift]);
                        a[i + shift] = y;
                    }
                }
                coef = mul(coef, prod[inverse][__builtin_ctz(~start)]);
            }
        }
        if (inverse) {
            const int rn = inv(n);
            for (int i = 0; i < n; ++i) {
                a[i] = mul(a[i], rn);
            }
        }
    }

    vector<int> product(vector<int> a, vector<int> b) const {
        if (a.empty() || b.empty()) {
            return {};
        }
        const int sz = a.size() + b.size() - 1;
        const int lg = 32 - __builtin_clz(sz - 1), n = 1 << lg;
        a.resize(n);
        b.resize(n);
        fft<false>(a.data(), lg);
        fft<false>(b.data(), lg);
        for (int i = 0; i < n; ++i) {
            a[i] = mul(a[i], b[i]);
        }
        fft<true>(a.data(), lg);
        a.resize(sz);
        return a;
    }

    vector<int> square(vector<int> a) const {
        if (a.empty()) {
            return {};
        }
        const int sz = a.size() + a.size() - 1;
        const int lg = 32 - __builtin_clz(sz - 1), n = 1 << lg;
        a.resize(n);
        fft<false>(a.data(), lg);
        for (int i = 0; i < n; ++i) {
            a[i] = mul(a[i], a[i]);
        }
        fft<true>(a.data(), lg);
        a.resize(sz);
        return a;
    }

    static int find_root() {
        for (int root = 2; ; ++root) {
            if (power(root, (1 << max_lev)) == 1 && power(root, (1 << (max_lev - 1))) != 1) {
                return root;
            }
        }
    }

    static inline void inc(int &x, int y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        }
    }

    static inline void dec(int &x, int y) {
        x -= y;
        if (x < 0) {
            x += mod;
        }
    }

    static inline int mul(int x, int y) {
        return (1LL * x * y) % mod;
    }

    static int power(int x, int y) {
        if (y == 0) {
            return 1;
        }
        if (y % 2 == 0) {
            return power(mul(x, x), y / 2);
        }
        return mul(x, power(x, y - 1));
    }

    static int inv(int x) {
        return power(x, mod - 2);
    }
};

NTT<mod> ntt;

inline void inc(int &x, int y) {
    x += y;
    if (x >= mod) {
        x -= mod;
    }
}

inline void dec(int &x, int y) {
    x -= y;
    if (x < 0) {
        x += mod;
    }
}

inline int mul(int x) {
    return x;
}

template<typename... Args>
inline int mul(int x, Args... args) {
    return (1LL * x * mul(args...)) % mod;
}

int power(int a, int b) {
    int res = 1 % mod;
    while (b) {
        if (b % 2) {
            res = mul(res, a);
        }
        b /= 2;
        a = mul(a, a);
    }
    return res;
}

int inv(int x) {
    return power(x, mod - 2);
}

string str_fraction(int x, int n = 20) {
    stringstream res;
    pair<int, int> best(x, 1);
    for (int j = 1; j < n; ++j) {
        best = min(best, {mul(x, j), j});
        best = min(best, {mod - mul(x, j), -j});
    }
    if (best.second < 0) {
        best.first *= -1;
        best.second *= -1;
    }
    res << best.first << "/" << best.second;
    return res.str();
}

const int max_f = 1500111;

int F[max_f], rf[max_f];

void get_all_f() {
    F[0] = rf[0] = 1;
    for (int i = 1; i < max_f; ++i) {
        F[i] = mul(i, F[i - 1]);
    }
    rf[max_f - 1] = inv(F[max_f - 1]);
    for (int i = max_f - 2; i > 0; --i) {
        rf[i] = mul(i + 1, rf[i + 1]);
    }
}

int get_c(int n, int k) {
    if (n < k || k < 0) {
        return 0;
    }
    return mul(F[n], mul(rf[k], rf[n - k]));
}

int get_c(int n, int k1, int k2) {
    if (n < k1 + k2 || k1 < 0 || k2 < 0) {
        return 0;
    }
    return mul(F[n], rf[k1], rf[k2], rf[n - k1 - k2]);
}

int n;
int a, b, c;
int d, e, f;
int g, h, i;

int solve() {
    int res = 0;
    const int k = g - b - e;
    const int l = a + d - h;
    const int m = i - f + a + b;
    if ((m + l) % 3) {
        return 0;
    }
    const int p = (m + l) / 3;
    const int q = p - l;
    vector<int> A(a + 1), B(a + 1);
    for (int y = 0; y <= a; ++y) {
        if (b - p - q + y < 0 || d - p + y < 0) {
            continue;
        }
        A[y] = mul(rf[y], rf[b - p - q + y], rf[d - p + y]);
    }
    for (int y = 0; y <= a; ++y) {
        if (p - a + y < 0 || e - q - a + y < 0) {
            continue;
        }
        B[y] = mul(rf[y], rf[p - a + y], rf[e - q - a + y]);
    }
    vector<int> C = ntt.product(A, B);
    for (int x = 0; x <= a; ++x) {
        if (q + x < 0 || q + x > b || c - d + p - e + q + x < 0 || c - d + p - e + q + x > c) {
            continue;
        }
        int coef = mul(F[a], F[b], F[c], rf[x], rf[q + x], rf[c - d + p - e + q + x]);
        inc(res, mul(coef, C[a - x]));
    }
    res = mul(res, get_c(n, a, b));
    return res;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    get_all_f();
    cin >> n;
    cin >> a >> b >> c;
    cin >> d >> e >> f;
    cin >> g >> h >> i;
    cout << solve() << "\n";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 16ms
memory: 15220kb

input:

2
2 0 0
1 1 0
1 0 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 12ms
memory: 15168kb

input:

3
0 1 2
3 0 0
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 33ms
memory: 18044kb

input:

333333
111111 111111 111111
111111 111111 111111
111111 111111 111111

output:

383902959

result:

ok 1 number(s): "383902959"

Test #4:

score: 0
Accepted
time: 123ms
memory: 28848kb

input:

1500000
500000 500000 500000
500000 500000 500000
500000 500000 500000

output:

355543262

result:

ok 1 number(s): "355543262"

Test #5:

score: 0
Accepted
time: 121ms
memory: 28780kb

input:

1499999
499999 499999 500001
499999 499999 500001
499999 499999 500001

output:

934301164

result:

ok 1 number(s): "934301164"

Test #6:

score: 0
Accepted
time: 16ms
memory: 15168kb

input:

1500000
1 0 1499999
1499999 1 0
0 1499999 1

output:

1500000

result:

ok 1 number(s): "1500000"

Test #7:

score: -100
Runtime Error

input:

1499999
0 749999 750000
750000 0 749999
749999 750000 0

output:


result: