QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#181028 | #6323. Range NEQ | ucup-team228# | AC ✓ | 105ms | 35740kb | C++20 | 5.3kb | 2023-09-16 15:16:56 | 2023-09-16 15:16:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
typedef long long ll;
typedef pair<int, int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
std::ostream& operator << (std::ostream& os, const vector<T>& a) {
for (const T& x : a) {
os << x << ' ';
}
return os;
}
template <int m>
struct mint {
int x = 0;
mint(int64_t a = 0) { if (a < 0) a = a % m + m; if (a >= m) a %= m; x = a; }
friend istream& operator>>(istream& in, mint& a) { int64_t y; in >> y; a = y; return in; }
friend ostream& operator<<(ostream& out, mint a) { return out << a.x; }
explicit operator int() const { return x; }
static int mod_inv(int a, int mod = m) {
int g = mod, r = a, z = 0, y = 1;
while (r != 0) { int q = g / r; g %= r; swap(g, r); z -= q * y; swap(z, y); }
return z < 0 ? z + mod : z;
}
mint inv() const { return mod_inv(x, m); }
friend mint binpow(mint a, int64_t b) { mint res = 1; while (b) { if (b & 1) res *= a; b >>= 1; a *= a; } return res; }
mint pow(int64_t b) const { return binpow(*this, b); }
mint operator-() const { return x ? m - x : 0; }
mint& operator+=(const mint& a) { x += a.x; if (x >= m) x -= m; return *this; }
mint& operator-=(const mint& a) { x -= a.x; if (x < 0) x += m; return *this; }
static unsigned fast_mod(uint64_t x, unsigned mod = m) {
#if defined(_WIN32) && !defined(_WIN64)
// Optimized mod for Codeforces 32-bit machines.
// x must be less than 2^32 * mod for this to work, so that x / mod fits in a 32-bit integer.
unsigned x_high = x >> 32, x_low = (unsigned) x; unsigned quot, rem;
asm("divl %4\n" : "=a" (quot), "=d" (rem) : "d" (x_high), "a" (x_low), "r" (mod));
return rem;
#else
return x % mod;
#endif
}
mint& operator*=(const mint& a) { x = fast_mod((uint64_t) x * a.x); return *this; }
mint& operator/=(const mint& a) { return *this *= a.inv(); }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
mint& operator++() { x = x == m - 1 ? 0 : x + 1; return *this; }
mint& operator--() { x = x == 0 ? m - 1 : x - 1; return *this; }
mint operator++(int) { mint a = *this; ++*this; return a; }
mint operator--(int) { mint a = *this; --*this; return a; }
bool operator==(const mint& a) const { return x == a.x; }
bool operator!=(const mint& a) const { return x != a.x; }
};
const int mod = 998244353; // 985661441
const int K = 1 << 21; // be careful
const mint<mod> root = binpow(mint<mod>(3), (mod - 1) / K);
// 3 is a primitive root modulo mod
typedef vector<mint<mod>> poly;
mint<mod> prec_w[K / 2];
mint<mod> w[K];
bool initialized = 0;
void init() {
if (initialized) {
return;
}
initialized = 1;
prec_w[0] = 1;
for (int i = 1; i < K / 2; i++) {
prec_w[i] = prec_w[i - 1] * root;
}
for (int i = 1; i < K; i *= 2) {
for (int j = 0; j < i; j++) {
w[i + j] = prec_w[K / (2 * i) * j];
}
}
}
void fft(mint<mod>* in, mint<mod>* out, int n, int k = 1) {
//cout << n << endl;
if (n == 1) {
*out = *in;
return;
}
n /= 2;
fft(in, out, n, 2 * k);
fft(in + k, out + n, n, 2 * k);
for (int i = 0; i < n; i++) {
mint<mod> t = out[i + n] * w[i + n];
out[i + n] = out[i] - t;
out[i] += t;
}
}
poly eval(poly& a) {
while (__builtin_popcount(a.size()) != 1) {
a.push_back(0);
}
poly res(a.size());
fft(a.data(), res.data(), a.size());
return res;
}
poly inter(poly a) {
int n = a.size();
poly res(n);
fft(a.data(), res.data(), n);
for (int i = 0; i < n; i++) {
res[i] /= n;
}
reverse(res.begin() + 1, res.end());
return res;
}
using Mint = mint<mod>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int N = n * m;
vector<Mint> fact(N + 1), rfact(N + 1);
fact[0] = 1;
for (int i = 1; i <= N; ++i) {
fact[i] = i * fact[i - 1];
}
rfact[N] = fact[N].inv();
for (int i = N; i > 0; --i) {
rfact[i - 1] = rfact[i] * i;
}
auto C = [&](int n1, int k1) {
return fact[n1] * rfact[k1] * rfact[n1 - k1];
};
init();
int L = 1 << 20;
vector<Mint> a(L, 0);
vector<Mint> res(L);
for (int i = 0; i <= m; ++i) {
if (i & 1) {
a[i] = mod - C(m, i) * C(m, i) * fact[i];
} else {
a[i] = C(m, i) * C(m, i) * fact[i];
}
}
fft(a.data(), res.data(), L);
for (int i = 0; i < L; ++i) {
res[i] = res[i].pow(n);
}
vector<Mint> b(L, 0);
fft(res.data(), b.data(), L);
reverse(b.begin() + 1, b.end());
for (int i = 0; i < L; ++i) {
b[i] /= L;
}
Mint ans = 0;
for (int k = 0; k <= N; ++k) {
ans += b[N - k] * fact[k];
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 62ms
memory: 27692kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 59ms
memory: 27628kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 81ms
memory: 27948kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 61ms
memory: 27704kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 61ms
memory: 27692kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 64ms
memory: 27700kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 71ms
memory: 27700kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 69ms
memory: 27740kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 69ms
memory: 27692kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 58ms
memory: 27672kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 67ms
memory: 27700kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 62ms
memory: 27760kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 70ms
memory: 27624kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 62ms
memory: 27704kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 64ms
memory: 27576kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 63ms
memory: 27632kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 69ms
memory: 27692kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: 0
Accepted
time: 100ms
memory: 35740kb
input:
1000 1000
output:
720037464
result:
ok 1 number(s): "720037464"
Test #19:
score: 0
Accepted
time: 71ms
memory: 27960kb
input:
72 42
output:
638177567
result:
ok 1 number(s): "638177567"
Test #20:
score: 0
Accepted
time: 73ms
memory: 27640kb
input:
15 19
output:
663050288
result:
ok 1 number(s): "663050288"
Test #21:
score: 0
Accepted
time: 72ms
memory: 27880kb
input:
68 89
output:
94365047
result:
ok 1 number(s): "94365047"
Test #22:
score: 0
Accepted
time: 73ms
memory: 27912kb
input:
92 37
output:
652605307
result:
ok 1 number(s): "652605307"
Test #23:
score: 0
Accepted
time: 71ms
memory: 27876kb
input:
61 87
output:
498277867
result:
ok 1 number(s): "498277867"
Test #24:
score: 0
Accepted
time: 71ms
memory: 27904kb
input:
81 40
output:
133095344
result:
ok 1 number(s): "133095344"
Test #25:
score: 0
Accepted
time: 65ms
memory: 27652kb
input:
7 91
output:
524164813
result:
ok 1 number(s): "524164813"
Test #26:
score: 0
Accepted
time: 78ms
memory: 27696kb
input:
31 18
output:
361233485
result:
ok 1 number(s): "361233485"
Test #27:
score: 0
Accepted
time: 76ms
memory: 28024kb
input:
74 54
output:
500686087
result:
ok 1 number(s): "500686087"
Test #28:
score: 0
Accepted
time: 71ms
memory: 27620kb
input:
32 2
output:
586504335
result:
ok 1 number(s): "586504335"
Test #29:
score: 0
Accepted
time: 88ms
memory: 31380kb
input:
656 718
output:
346764298
result:
ok 1 number(s): "346764298"
Test #30:
score: 0
Accepted
time: 82ms
memory: 29196kb
input:
254 689
output:
358078813
result:
ok 1 number(s): "358078813"
Test #31:
score: 0
Accepted
time: 83ms
memory: 31584kb
input:
713 674
output:
914437613
result:
ok 1 number(s): "914437613"
Test #32:
score: 0
Accepted
time: 78ms
memory: 28552kb
input:
136 698
output:
56687290
result:
ok 1 number(s): "56687290"
Test #33:
score: 0
Accepted
time: 85ms
memory: 29004kb
input:
369 401
output:
312325811
result:
ok 1 number(s): "312325811"
Test #34:
score: 0
Accepted
time: 78ms
memory: 28160kb
input:
280 204
output:
280012063
result:
ok 1 number(s): "280012063"
Test #35:
score: 0
Accepted
time: 87ms
memory: 29220kb
input:
904 225
output:
162909174
result:
ok 1 number(s): "162909174"
Test #36:
score: 0
Accepted
time: 95ms
memory: 33940kb
input:
855 928
output:
39885159
result:
ok 1 number(s): "39885159"
Test #37:
score: 0
Accepted
time: 91ms
memory: 29204kb
input:
503 365
output:
745115888
result:
ok 1 number(s): "745115888"
Test #38:
score: 0
Accepted
time: 82ms
memory: 33004kb
input:
646 996
output:
610925577
result:
ok 1 number(s): "610925577"
Test #39:
score: 0
Accepted
time: 99ms
memory: 35064kb
input:
990 918
output:
203469632
result:
ok 1 number(s): "203469632"
Test #40:
score: 0
Accepted
time: 94ms
memory: 34936kb
input:
961 949
output:
169566857
result:
ok 1 number(s): "169566857"
Test #41:
score: 0
Accepted
time: 95ms
memory: 34824kb
input:
946 932
output:
352423195
result:
ok 1 number(s): "352423195"
Test #42:
score: 0
Accepted
time: 92ms
memory: 34684kb
input:
903 981
output:
196309824
result:
ok 1 number(s): "196309824"
Test #43:
score: 0
Accepted
time: 89ms
memory: 34652kb
input:
916 988
output:
487208972
result:
ok 1 number(s): "487208972"
Test #44:
score: 0
Accepted
time: 105ms
memory: 35548kb
input:
982 982
output:
387421488
result:
ok 1 number(s): "387421488"
Test #45:
score: 0
Accepted
time: 91ms
memory: 34684kb
input:
955 911
output:
955637031
result:
ok 1 number(s): "955637031"
Test #46:
score: 0
Accepted
time: 91ms
memory: 34696kb
input:
906 999
output:
798469943
result:
ok 1 number(s): "798469943"
Test #47:
score: 0
Accepted
time: 92ms
memory: 35224kb
input:
982 975
output:
193506289
result:
ok 1 number(s): "193506289"
Test #48:
score: 0
Accepted
time: 94ms
memory: 34948kb
input:
921 991
output:
431202149
result:
ok 1 number(s): "431202149"