QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415192 | #7632. Balanced Arrays | caijianhong | AC ✓ | 90ms | 47732kb | C++23 | 4.9kb | 2024-05-20 15:37:33 | 2024-05-20 15:37:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
template <class T>
using must_int = enable_if_t<is_integral<T>::value, int>;
template <unsigned umod>
struct modint { /*{{{*/
static constexpr int mod = umod;
unsigned v;
modint() : v(0) {}
template <class T, must_int<T> = 0>
modint(T x) {
x %= mod;
v = x < 0 ? x + mod : x;
}
modint operator+() const { return *this; }
modint operator-() const { return modint() - *this; }
friend int raw(const modint &self) { return self.v; }
friend ostream &operator<<(ostream &os, const modint &self) {
return os << raw(self);
}
modint &operator+=(const modint &rhs) {
v += rhs.v;
if (v >= umod) v -= umod;
return *this;
}
modint &operator-=(const modint &rhs) {
v -= rhs.v;
if (v >= umod) v += umod;
return *this;
}
modint &operator*=(const modint &rhs) {
v = 1ull * v * rhs.v % umod;
return *this;
}
modint &operator/=(const modint &rhs) {
assert(rhs.v);
return *this *= qpow(rhs, mod - 2);
}
template <class T, must_int<T> = 0>
friend modint qpow(modint a, T b) {
modint r = 1;
for (; b; b >>= 1, a *= a)
if (b & 1) r *= a;
return r;
}
friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
bool operator==(const modint &rhs) const { return v == rhs.v; }
bool operator!=(const modint &rhs) const { return v != rhs.v; }
}; /*}}}*/
typedef modint<998244353> mint;
int glim(int n) { return 1 << (32 - __builtin_clz(n - 1)); }
int bitctz(int n) { return __builtin_ctz(n); }
template <class mint, int G>
struct NTT_env {
vector<mint> w{1};
void init(int n) {
if (w.size() < n) w.reserve(n);
while (w.size() < n) {
int m = w.size();
mint wn = qpow(mint(G), (mint::mod - 1) / m >> 2);
w.resize(m << 1);
for (int i = m; i < m << 1; i++) w[i] = wn * w[i ^ m];
}
}
void dif(vector<mint> &a) {
int n = a.size();
init(n);
for (int len = n, k = n >> 1; k >= 1; len = k, k >>= 1) {
for (int i = 0, t = 0; i < n; i += len, t++) {
for (int j = 0; j < k; j++) {
mint x = a[i + j], y = a[i + j + k] * w[t];
a[i + j] = x + y, a[i + j + k] = x - y;
}
}
}
}
void dit(vector<mint> &a) {
int n = a.size();
init(n);
for (int k = 1, len = 2; len <= n; k = len, len <<= 1) {
for (int i = 0, t = 0; i < n; i += len, t++) {
for (int j = 0; j < k; j++) {
mint x = a[i + j], y = a[i + j + k];
a[i + j] = x + y, a[i + j + k] = (x - y) * w[t];
}
}
}
mint iv = mint(1) / n;
for (int i = 0; i < n; i++) a[i] *= iv;
reverse(a.begin() + 1, a.end());
}
};
vector<mint> convolution(vector<mint> a, vector<mint> b) {
static NTT_env<mint, 3> ntt;
int rlen = a.size() + b.size() - 1, len = glim(rlen);
a.resize(len), ntt.dif(a);
b.resize(len), ntt.dif(b);
for (int i = 0; i < len; i++) a[i] *= b[i];
ntt.dit(a), a.resize(rlen);
return a;
}
template <int N>
struct C_prime { /*{{{*/
mint fac[N + 10], ifac[N + 10];
C_prime() {
for (int i = raw(fac[0] = 1); i <= N; i++) fac[i] = fac[i - 1] * i;
ifac[N] = 1 / fac[N];
for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i;
}
mint operator()(int n, int m) {
return n >= m ? fac[n] * ifac[m] * ifac[n - m] : 0;
}
}; /*}}}*/
int n, m;
C_prime<2000010> binom;
mint f[2000010], g[2000010];
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m;
mint ans = 1;
while (false) {
for (int i = 1; i <= m; i++) {
for (int k = 1; k <= i; k++) {
// ans += binom(i - 1, k - 1) * binom(i, k - 1) *
// binom(n - 2 * k + 2 * i + 1, 2 * i) * binom.ifac[k] *
// binom.fac[k - 1];
ans += binom.fac[i - 1] * binom.ifac[i - k] * binom.ifac[k - 1] *
binom.fac[i] * binom.ifac[i - k + 1] *
binom.fac[n - 2 * k + 2 * i + 1] * binom.ifac[2 * i] *
binom.ifac[n - 2 * k + 1] * binom.ifac[k];
}
}
}
int lim = (n + 1) >> 1;
// i - k
for (int i = 0; i <= m - 1; i++) f[i] = binom.ifac[i] * binom.ifac[i + 1] * binom.fac[n + 2 * i + 1];
// k
for (int i = 1; i <= lim; i++) g[i] = binom.ifac[i] * binom.ifac[i - 1] * binom.ifac[n - 2 * i + 1];
vector<mint> ret = convolution(vector<mint>(f, f + m), vector<mint>(g, g + lim + 1));
for (int i = 1; i < ret.size() && i <= m; i++) {
ans += binom.fac[i - 1] * binom.fac[i] * binom.ifac[2 * i] * ret[i];
debug("i = %d, ans += %d\n", i, raw(binom.fac[i - 1] * binom.fac[i] * binom.ifac[2 * i] * ret[i]));
}
cout << ans << endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 34836kb
input:
2 2
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 86ms
memory: 47592kb
input:
500000 500000
output:
984531374
result:
ok 1 number(s): "984531374"
Test #3:
score: 0
Accepted
time: 26ms
memory: 38504kb
input:
500000 1
output:
219705876
result:
ok 1 number(s): "219705876"
Test #4:
score: 0
Accepted
time: 50ms
memory: 40832kb
input:
1 500000
output:
500001
result:
ok 1 number(s): "500001"
Test #5:
score: 0
Accepted
time: 85ms
memory: 47664kb
input:
500000 353535
output:
33730077
result:
ok 1 number(s): "33730077"
Test #6:
score: 0
Accepted
time: 85ms
memory: 47296kb
input:
353535 500000
output:
182445298
result:
ok 1 number(s): "182445298"
Test #7:
score: 0
Accepted
time: 89ms
memory: 47656kb
input:
499999 499999
output:
933220940
result:
ok 1 number(s): "933220940"
Test #8:
score: 0
Accepted
time: 86ms
memory: 47676kb
input:
499999 499998
output:
899786345
result:
ok 1 number(s): "899786345"
Test #9:
score: 0
Accepted
time: 85ms
memory: 47484kb
input:
377773 400009
output:
206748715
result:
ok 1 number(s): "206748715"
Test #10:
score: 0
Accepted
time: 52ms
memory: 41468kb
input:
499999 100001
output:
482775773
result:
ok 1 number(s): "482775773"
Test #11:
score: 0
Accepted
time: 90ms
memory: 47620kb
input:
444445 488884
output:
70939759
result:
ok 1 number(s): "70939759"
Test #12:
score: 0
Accepted
time: 85ms
memory: 47544kb
input:
488885 444449
output:
591315327
result:
ok 1 number(s): "591315327"
Test #13:
score: 0
Accepted
time: 31ms
memory: 38576kb
input:
500000 111
output:
313439156
result:
ok 1 number(s): "313439156"
Test #14:
score: 0
Accepted
time: 86ms
memory: 47304kb
input:
333333 444444
output:
403492103
result:
ok 1 number(s): "403492103"
Test #15:
score: 0
Accepted
time: 84ms
memory: 47732kb
input:
499994 343433
output:
334451699
result:
ok 1 number(s): "334451699"
Test #16:
score: 0
Accepted
time: 90ms
memory: 47520kb
input:
477774 411113
output:
63883341
result:
ok 1 number(s): "63883341"
Test #17:
score: 0
Accepted
time: 41ms
memory: 41376kb
input:
123456 432109
output:
238795570
result:
ok 1 number(s): "238795570"
Test #18:
score: 0
Accepted
time: 85ms
memory: 46872kb
input:
131331 467777
output:
834790039
result:
ok 1 number(s): "834790039"
Test #19:
score: 0
Accepted
time: 35ms
memory: 38512kb
input:
500000 2
output:
304727284
result:
ok 1 number(s): "304727284"
Test #20:
score: 0
Accepted
time: 17ms
memory: 34872kb
input:
1111 111
output:
98321603
result:
ok 1 number(s): "98321603"
Test #21:
score: 0
Accepted
time: 86ms
memory: 47396kb
input:
416084 493105
output:
916827025
result:
ok 1 number(s): "916827025"
Test #22:
score: 0
Accepted
time: 31ms
memory: 37432kb
input:
53888 138663
output:
57263952
result:
ok 1 number(s): "57263952"
Test #23:
score: 0
Accepted
time: 41ms
memory: 41892kb
input:
219161 382743
output:
304889787
result:
ok 1 number(s): "304889787"
Test #24:
score: 0
Accepted
time: 50ms
memory: 40820kb
input:
181392 318090
output:
12528742
result:
ok 1 number(s): "12528742"
Test #25:
score: 0
Accepted
time: 54ms
memory: 40724kb
input:
135930 422947
output:
554153000
result:
ok 1 number(s): "554153000"
Test #26:
score: 0
Accepted
time: 57ms
memory: 41024kb
input:
280507 210276
output:
812816587
result:
ok 1 number(s): "812816587"
Test #27:
score: 0
Accepted
time: 83ms
memory: 47176kb
input:
253119 420465
output:
124024302
result:
ok 1 number(s): "124024302"
Test #28:
score: 0
Accepted
time: 56ms
memory: 41372kb
input:
446636 97448
output:
150388382
result:
ok 1 number(s): "150388382"
Test #29:
score: 0
Accepted
time: 52ms
memory: 41016kb
input:
284890 126665
output:
786559507
result:
ok 1 number(s): "786559507"
Test #30:
score: 0
Accepted
time: 21ms
memory: 36400kb
input:
186708 28279
output:
607509026
result:
ok 1 number(s): "607509026"
Extra Test:
score: 0
Extra Test Passed