QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556965 | #6323. Range NEQ | ucup-team3691 | TL | 51ms | 4496kb | C++14 | 3.9kb | 2024-09-10 22:49:31 | 2024-09-10 22:49:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using ll = long long;
using ull = unsigned long long;
string to_string(const string &s) {
return '"' + s + '"';
}
string to_string(bool b) {
return b ? "true" : "false";
}
template <typename A, typename B>
string to_string(const pair<A, B> &p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename T>
string to_string(const T &v) {
string s = "{";
bool first = true;
for (const auto &it : v) {
if (!first)
s += ", ";
else
first = false;
s += to_string(it);
}
return s += "}";
}
void debug_out() {
cerr << endl;
}
template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
cerr << to_string(first) << " ";
debug_out(rest...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto startTime = high_resolution_clock::now();
int get_time() {
auto stopTime = chrono::high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(stopTime - startTime);
return duration.count(); // in ms
}
constexpr int MOD = 998244353;
constexpr int lgpow(int x, int p) {
int aux = x, ans = 1;
for (int i = 1; i <= p; i <<= 1) {
if (i & p)
ans = 1ll * ans * aux % MOD;
aux = 1ll * aux * aux % MOD;
}
return ans;
}
namespace NTT {
vector<int> ntt( vector<int> &a, int g ) {
if ( a.size() == 1 ) {
return vector<int>(1, a[0]);
}
vector<int> pa, oa;
for ( int i = 0; i < a.size(); i += 2 ) {
pa.push_back(a[i]);
oa.push_back(a[i + 1]);
}
pa = ntt(pa, 1ll * g * g % MOD);
oa = ntt(oa, 1ll * g * g % MOD);
vector<int> ra(a.size());
for ( int i = 0, p = 1; i < a.size() / 2; ++i, p = 1LL * p * g % MOD ) {
ra[i] = ( pa[i] + 1ll * oa[i] * p ) % MOD;
ra[i + a.size() / 2] = ( pa[i] - 1ll * oa[i] * p % MOD + MOD ) % MOD;
}
return ra;
}
vector<int> mul( vector<int> a, vector<int> b ) {
int n = a.size() + b.size() - 1;
int p2 = 1;
while ( p2 < n ) {
p2 *= 2;
}
n = p2;
while ( a.size() < n ) {
a.push_back(0);
}
while ( b.size() < n ) {
b.push_back(0);
}
auto ra = ntt(a, lgpow(3, MOD / n));
auto rb = ntt(b, lgpow(3, MOD / n));
for( int i = 0; i < ra.size(); ++i ) {
ra[i] = 1ll * ra[i] * rb[i] % MOD;
}
ra = ntt(ra, lgpow(lgpow(3, MOD - 2), MOD / n));
for( int i = 0; i < ra.size(); ++i ) {
ra[i] = 1ll * ra[i] * lgpow(ra.size(), MOD - 2) % MOD;
}
while ( !ra.back() )
ra.pop_back();
return ra;
}
};
void solve() {
int n, m;
cin >> n >> m;
std::vector<int> fact(n * m + 1, 1);
std::vector<int> ifact(n * m + 1, 1);
auto comb = [&](int n, int m) {
return 1LL * fact[n] * ifact[n - m] % MOD * ifact[m] % MOD;
};
for (int i = 1; i <= n * m; ++i) {
fact[i] = 1LL * fact[i - 1] * i % MOD;
}
ifact[n * m] = lgpow(fact[n * m], MOD - 2);
for (int i = n * m - 1; i >= 1; --i) {
ifact[i] = 1LL * ifact[i + 1] * (i + 1) % MOD;
}
vector<int> poly(1, 1);
vector<int> tmp(m + 1, 0);
for ( int i = 0; i <= m; ++i ) {
tmp[i] = 1ll * comb(m, i) * comb(m, i) % MOD * fact[i] % MOD;
}
for ( int p = 1; p <= n; p <<= 1 ) {
if ( p & n ) {
poly = NTT::mul(poly, tmp);
}
tmp = NTT::mul(tmp, tmp);
}
int ans = 0;
for ( int i = 0; i < poly.size(); ++i ) {
ans = (1ll * MOD + ans + (i % 2 ? -1 : 1) * 1ll * poly[i] * fact[(n * m - i)] % MOD) % MOD;
}
cout << ans << "\n";
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 51ms
memory: 4496kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: -100
Time Limit Exceeded
input:
1000 1000