QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415177 | #7632. Balanced Arrays | caijianhong | TL | 18ms | 19248kb | C++14 | 2.8kb | 2024-05-20 15:15:41 | 2024-05-20 15:15:41 |
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;
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;
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m;
mint ans = 1;
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];
debug("i = %d, k = %d, p1 = %d / %d, p2 = %d\n", i, k, raw(binom(i - 1, k - 1) * binom(i, k - 1)), k, raw(binom(n - 2 * k + 2 * i +1, 2 * i )));
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 18ms
memory: 19248kb
input:
2 2
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: -100
Time Limit Exceeded
input:
500000 500000