QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#863672#9870. ItemsliyelinTL 1548ms15692kbC++146.6kb2025-01-19 21:06:392025-01-19 21:06:52

Judging History

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

  • [2025-01-19 21:06:52]
  • 评测
  • 测评结果：TL
  • 用时：1548ms
  • 内存：15692kb
查看
  • [2025-01-19 21:06:39]
  • 提交

answer

#include <bits/stdc++.h>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (int i = (r); i >= (l); --i)
#define popc(x) __builtin_popcount(x)
#define allc(x) (x).begin(), (x).end()
#define SZ(v) (int)v.size()
#define PII pair<int, int>
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
bool Mbe;
template <typename A, typename B>
void chkmax(A &a, B b) {
    a = a > b ? a : b;
}
template <typename A, typename B>
void chkmin(A &a, B b) {
    a = a < b ? a : b;
}
namespace lyl {
    template<int MOD> struct modint {
        int val;
        constexpr modint(int v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; }
        constexpr int getmod() const { return MOD; }
        constexpr modint operator - () const noexcept { return val ? MOD - val : 0; }
        constexpr modint operator + (const modint &r) const noexcept { return modint(*this) += r; }
        constexpr modint operator - (const modint &r) const noexcept { return modint(*this) -= r; }
        constexpr modint operator * (const modint &r) const noexcept { return modint(*this) *= r; }
        constexpr modint operator / (const modint &r) const noexcept { return modint(*this) /= r; }
        constexpr modint &operator += (const modint &r) noexcept {
            val += r.val;
            if (val >= MOD) val -= MOD;
            return *this;
        }
        constexpr modint &operator -= (const modint &r) noexcept {
            val -= r.val;
            if (val < 0) val += MOD;
            return *this;
        }
        constexpr modint &operator *= (const modint &r) noexcept {
            val = 1ll * val * r.val % MOD;
            return *this;
        }
        constexpr modint &operator /= (const modint &r) noexcept {
            int a = r.val, b = MOD, u = 1, v = 0;
            while (b) {
                int t = a / b;
                a -= t * b, swap(a, b);
                u -= t * v, swap(u, v);
            }
            val = 1ll * val * u % MOD;
            if (val < 0) val += MOD;
            return *this;
        }
        constexpr bool operator < (const modint &r) const noexcept { return this->val < r.val; }
        constexpr bool operator == (const modint &r) const noexcept { return this->val == r.val; }
        constexpr bool operator != (const modint &r) const noexcept { return this->val != r.val; }
        friend constexpr istream &operator >> (istream &is, modint<MOD> &x) noexcept {
            is >> x.val;
            x.val %= MOD;
            if (x.val < 0) x.val += MOD;
            return is;
        }
        friend constexpr ostream &operator << (ostream &os, const modint<MOD> &x) noexcept { return os << x.val; }
        friend constexpr modint<MOD> modpow(const modint<MOD> &r, ll n) noexcept {
            if (n == 0) return 1;
            if (n < 0) return modpow(modinv(r), -n);
            auto t = modpow(r, n / 2);
            t = t * t;
            if (n & 1) t = t * r;
            return t;
        }
        friend constexpr modint<MOD> modinv(const modint<MOD> &r) noexcept {
            int a = r.val, b = MOD, u = 1, v = 0;
            while (b) {
                int t = a / b;
                a -= t * b, swap(a, b);
                u -= t * v, swap(u, v);
            }
            return modint<MOD>(u);
        }
    };
    const int mod = 998244353;
    using Z = modint<mod>;
    const int N = 8e5 + 5;
    const Z G = 3;
    const Z Gi = modinv(G);
    int n, a[N], rev[N];
    ll m;
    void change(Z *f, int n) {
        FOR (i, 0, n - 1) {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1)); 
            if (i < rev[i]) {
                swap(f[i], f[rev[i]]);
            }
        }
    }
    void NTT(Z *f, int n, int inv) {
        change(f, n);
        for (int k = 2; k <= n; k <<= 1) {
            Z wn = modpow(inv == -1 ? Gi : G, (mod - 1) / k);
            for (int i = 0; i < n; i += k) {
                Z w = 1;
                for (int p = i; p < i + k / 2; ++p) {
                    Z x = f[p], y = w * f[p + k / 2];
                    f[p] = x + y;
                    f[p + k / 2] = x - y;
                    w *= wn;
                }
            }
        }
        if (inv == -1) {
            Z t = modinv((Z)n);
            FOR (i, 0, n - 1) {
                f[i] *= t;
            }
        }
    }
    void mul(Z *f, Z *g, int len) {
        NTT(f, len, 1);
        NTT(g, len, 1);
        FOR (i, 0, len - 1) {
            f[i] *= g[i];
        }
        NTT(f, len, -1);
    }
    Z ans[N], tmp[N];
    void ksm(Z *f, int n, int k) {
        int len = 1;
        while (len <= (n << 1)) {
            len <<= 1;
        }
        memcpy(ans, f, sizeof(ans));
        --k;
        while (k) {
            if (k & 1) {
                memcpy(tmp, f, sizeof(tmp));
                mul(ans, tmp, len);
                FOR (i, 0, n) {
                    ans[i] = ans[i + n / 2];
                }
                FOR (i, n + 1, len - 1) {
                    ans[i] = 0;
                }
            }
            k >>= 1;
            memcpy(tmp, f, sizeof(tmp));
            mul(f, tmp, len);
            FOR (i, 0, n) {
                f[i] = f[i + n / 2];
            }
            FOR (i, n + 1, len - 1) {
                f[i] = 0;
            }
        }
    }
    Z F[N];
    void solve() {
        memset(F, 0, sizeof(F));
        memset(ans, 0, sizeof(ans));
        cin >> n >> m;
        FOR (i, 1, n) {
            cin >> a[i];
        }
        ll d = m / n;
        FOR (i, 1, n) {
            a[i] -= d;
        }
        m -= d * n;
        FOR (i, 1, n) {
            a[i] += n;
            F[a[i]] += 1;
        }
        // FOR (i, 0, n << 1) {
        //     cout << F[i] << ' ';
        // }
        // cout << '\n';
        ksm(F, n << 1, n);
        // FOR (i, 0, n << 2) {
        //     cout << ans[i] << ' ';
        // }
        // cout << '\n';
        if (ans[n + m] != 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}
bool Meb;
int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        lyl::solve();
    }
    // cerr << "Space: " << abs(&Meb - &Mbe) / 1024.0 / 1024.0 << "MB\n";
    // cerr << "Time: " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 15232kb

input:

4
5 25
0 0 0 0 5
5 11
4 4 4 5 5
5 0
1 2 3 4 5
5 25
0 1 2 3 4

output:

Yes
No
No
No

result:

ok 4 token(s): yes count is 1, no count is 3

Test #2:

score: 0
Accepted
time: 1548ms
memory: 15692kb

input:

1314
1 0
0
1 0
1
1 1
0
1 1
1
2 0
0 0
2 0
0 1
2 0
0 2
2 0
1 0
2 0
1 1
2 0
1 2
2 0
2 0
2 0
2 1
2 0
2 2
2 1
0 0
2 1
0 1
2 1
0 2
2 1
1 0
2 1
1 1
2 1
1 2
2 1
2 0
2 1
2 1
2 1
2 2
2 2
0 0
2 2
0 1
2 2
0 2
2 2
1 0
2 2
1 1
2 2
1 2
2 2
2 0
2 2
2 1
2 2
2 2
2 3
0 0
2 3
0 1
2 3
0 2
2 3
1 0
2 3
1 1
2 3
1 2
2 3
2 0...

output:

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
Yes
Yes...

result:

ok 1314 token(s): yes count is 732, no count is 582

Test #3:

score: -100
Time Limit Exceeded

input:

10000
4 1
0 0 0 0
4 1
0 0 0 1
4 1
0 0 0 2
4 1
0 0 0 3
4 1
0 0 0 4
4 1
0 0 1 0
4 1
0 0 1 1
4 1
0 0 1 2
4 1
0 0 1 3
4 1
0 0 1 4
4 1
0 0 2 0
4 1
0 0 2 1
4 1
0 0 2 2
4 1
0 0 2 3
4 1
0 0 2 4
4 1
0 0 3 0
4 1
0 0 3 1
4 1
0 0 3 2
4 1
0 0 3 3
4 1
0 0 3 4
4 1
0 0 4 0
4 1
0 0 4 1
4 1
0 0 4 2
4 1
0 0 4 3
4 1
0 ...

output:

No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
...

result:
English 繁體中文 简体中文

Server Time: 2025-01-20 00:17:57 | OpenSource Project