QOJ.ac
QOJ
QOJ is currently under a maintenance. It might be unavailable in the following a few hours.
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#840375 | #8728. Tablica | jiangly (Lingyu Jiang) | 100 ✓ | 437ms | 109052kb | C++23 | 8.2kb | 2025-01-02 17:50:12 | 2025-01-02 17:50:13 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
template<class T>
constexpr T power(T a, u64 b, T res = 1) {
for (; b != 0; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
return u64(a) * b % P;
}
template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
res %= P;
return res;
}
constexpr i64 safeMod(i64 x, i64 m) {
x %= m;
if (x < 0) {
x += m;
}
return x;
}
constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
a = safeMod(a, b);
if (a == 0) {
return {b, 0};
}
i64 s = b, t = a;
i64 m0 = 0, m1 = 1;
while (t) {
i64 u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(s, t);
std::swap(m0, m1);
}
if (m0 < 0) {
m0 += b / s;
}
return {s, m0};
}
template<std::unsigned_integral U, U P>
struct ModIntBase {
public:
constexpr ModIntBase() : x(0) {}
template<std::unsigned_integral T>
constexpr ModIntBase(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr ModIntBase(T x_) {
using S = std::make_signed_t<U>;
S v = x_ % S(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static U mod() {
return P;
}
constexpr U val() const {
return x;
}
constexpr ModIntBase operator-() const {
ModIntBase res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr ModIntBase inv() const {
return power(*this, mod() - 2);
}
constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
x = mulMod<mod()>(x, rhs.val());
return *this;
}
constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
return *this *= rhs.inv();
}
friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
return os << a.val();
}
friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() <=> rhs.val();
}
private:
U x;
};
template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;
struct Barrett {
public:
Barrett(u32 m_) : m(m_), im((u64)(-1) / m_ + 1) {}
constexpr u32 mod() const {
return m;
}
constexpr u32 mul(u32 a, u32 b) const {
u64 z = a;
z *= b;
u64 x = u64((u128(z) * im) >> 64);
u32 v = u32(z - x * m);
if (m <= v) {
v += m;
}
return v;
}
private:
u32 m;
u64 im;
};
template<u32 Id>
struct DynModInt {
public:
constexpr DynModInt() : x(0) {}
template<std::unsigned_integral T>
constexpr DynModInt(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr DynModInt(T x_) {
int v = x_ % int(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static void setMod(u32 m) {
bt = m;
}
static u32 mod() {
return bt.mod();
}
constexpr u32 val() const {
return x;
}
constexpr DynModInt operator-() const {
DynModInt res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr DynModInt inv() const {
auto v = invGcd(x, mod());
assert(v.first == 1);
return v.second;
}
constexpr DynModInt &operator*=(const DynModInt &rhs) & {
x = bt.mul(x, rhs.val());
return *this;
}
constexpr DynModInt &operator+=(const DynModInt &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr DynModInt &operator-=(const DynModInt &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr DynModInt &operator/=(const DynModInt &rhs) & {
return *this *= rhs.inv();
}
friend constexpr DynModInt operator*(DynModInt lhs, const DynModInt &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr DynModInt operator+(DynModInt lhs, const DynModInt &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr DynModInt operator-(DynModInt lhs, const DynModInt &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr DynModInt operator/(DynModInt lhs, const DynModInt &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, DynModInt &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const DynModInt &a) {
return os << a.val();
}
friend constexpr bool operator==(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() <=> rhs.val();
}
private:
u32 x;
static Barrett bt;
};
template<u32 Id>
Barrett DynModInt<Id>::bt = 998244353;
using Z = ModInt<1000000007>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
int L = std::max(N, M);
std::vector dp(L + 1, std::vector<Z>(L + 1));
std::vector f1(L + 1, std::vector<Z>(L + 1));
std::vector f2(L + 1, std::vector<Z>(L + 1));
dp[0][0] = 1;
for (int s = 1; s <= N + M; s++) {
for (int i = std::max(1, s - L); i <= std::min(s - 1, L); i++) {
int j = s - i;
// deg = 1
dp[i][j] += dp[i - 1][j - 1] * j;
dp[i][j] += f1[j][i - 1];
// deg = 2
if (j >= 2) {
dp[i][j] += dp[i - 1][j - 2] * (j * (j - 1) / 2);
}
dp[i][j] += f1[j - 1][i - 1] * j;
dp[i][j] += f2[j][i - 1];
// deg = 1
f1[i][j] += dp[i - 1][j - 1] * j * i;
f1[i][j] += f1[j][i - 1] * i;
if (i >= 2) {
f2[i][j] += dp[i - 2][j - 1] * j * (i * (i - 1) / 2);
if (j >= 2) {
f2[i][j] += dp[i - 2][j - 2] * j * (j - 1) * (i * (i - 1) / 2);
}
f2[i][j] += f1[j - 1][i - 2] * j * i * (i - 1);
f2[i][j] += f2[j][i - 2] * i * (i - 1);
}
}
}
std::cout << dp[N][M] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3764kb
input:
5 6
output:
456750
result:
ok 1 number(s): "456750"
Test #2:
score: 10
Accepted
time: 1ms
memory: 3544kb
input:
6 6
output:
5464710
result:
ok 1 number(s): "5464710"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3580kb
input:
3 5
output:
270
result:
ok 1 number(s): "270"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3840kb
input:
3 6
output:
90
result:
ok 1 number(s): "90"
Test #5:
score: 10
Accepted
time: 0ms
memory: 3608kb
input:
4 6
output:
14580
result:
ok 1 number(s): "14580"
Test #6:
score: 10
Accepted
time: 0ms
memory: 3600kb
input:
3 4
output:
270
result:
ok 1 number(s): "270"
Subtask #2:
score: 18
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 18
Accepted
time: 1ms
memory: 3588kb
input:
50 49
output:
750700714
result:
ok 1 number(s): "750700714"
Test #8:
score: 18
Accepted
time: 1ms
memory: 3648kb
input:
50 50
output:
630532893
result:
ok 1 number(s): "630532893"
Test #9:
score: 18
Accepted
time: 0ms
memory: 3632kb
input:
41 34
output:
800856205
result:
ok 1 number(s): "800856205"
Test #10:
score: 18
Accepted
time: 0ms
memory: 3576kb
input:
39 41
output:
541550932
result:
ok 1 number(s): "541550932"
Test #11:
score: 18
Accepted
time: 0ms
memory: 3612kb
input:
38 46
output:
651393374
result:
ok 1 number(s): "651393374"
Test #12:
score: 18
Accepted
time: 0ms
memory: 3628kb
input:
37 39
output:
746919932
result:
ok 1 number(s): "746919932"
Test #13:
score: 18
Accepted
time: 0ms
memory: 3684kb
input:
30 50
output:
214086425
result:
ok 1 number(s): "214086425"
Test #14:
score: 18
Accepted
time: 0ms
memory: 3576kb
input:
50 41
output:
193351204
result:
ok 1 number(s): "193351204"
Test #15:
score: 18
Accepted
time: 0ms
memory: 3612kb
input:
44 32
output:
63855946
result:
ok 1 number(s): "63855946"
Test #16:
score: 18
Accepted
time: 1ms
memory: 3672kb
input:
45 42
output:
266239299
result:
ok 1 number(s): "266239299"
Subtask #3:
score: 31
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #17:
score: 31
Accepted
time: 0ms
memory: 4020kb
input:
199 200
output:
841552647
result:
ok 1 number(s): "841552647"
Test #18:
score: 31
Accepted
time: 2ms
memory: 4272kb
input:
200 200
output:
157842226
result:
ok 1 number(s): "157842226"
Test #19:
score: 31
Accepted
time: 2ms
memory: 3952kb
input:
156 199
output:
216453917
result:
ok 1 number(s): "216453917"
Test #20:
score: 31
Accepted
time: 2ms
memory: 4044kb
input:
161 199
output:
539960909
result:
ok 1 number(s): "539960909"
Test #21:
score: 31
Accepted
time: 2ms
memory: 3992kb
input:
194 160
output:
764024671
result:
ok 1 number(s): "764024671"
Test #22:
score: 31
Accepted
time: 2ms
memory: 4096kb
input:
184 195
output:
117763744
result:
ok 1 number(s): "117763744"
Test #23:
score: 31
Accepted
time: 0ms
memory: 4208kb
input:
152 174
output:
350941677
result:
ok 1 number(s): "350941677"
Test #24:
score: 31
Accepted
time: 2ms
memory: 3996kb
input:
195 186
output:
130526660
result:
ok 1 number(s): "130526660"
Test #25:
score: 31
Accepted
time: 2ms
memory: 4212kb
input:
173 159
output:
754934766
result:
ok 1 number(s): "754934766"
Test #26:
score: 31
Accepted
time: 2ms
memory: 4060kb
input:
194 170
output:
956364877
result:
ok 1 number(s): "956364877"
Subtask #4:
score: 41
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 41
Accepted
time: 437ms
memory: 109052kb
input:
3000 2999
output:
5195706
result:
ok 1 number(s): "5195706"
Test #28:
score: 41
Accepted
time: 430ms
memory: 108900kb
input:
3000 3000
output:
224347336
result:
ok 1 number(s): "224347336"
Test #29:
score: 41
Accepted
time: 383ms
memory: 99796kb
input:
2854 2864
output:
513408195
result:
ok 1 number(s): "513408195"
Test #30:
score: 41
Accepted
time: 424ms
memory: 101236kb
input:
2887 2803
output:
58832696
result:
ok 1 number(s): "58832696"
Test #31:
score: 41
Accepted
time: 404ms
memory: 103756kb
input:
2800 2925
output:
804387597
result:
ok 1 number(s): "804387597"
Test #32:
score: 41
Accepted
time: 414ms
memory: 98236kb
input:
2842 2813
output:
971828715
result:
ok 1 number(s): "971828715"
Test #33:
score: 41
Accepted
time: 402ms
memory: 107208kb
input:
2808 2972
output:
329457042
result:
ok 1 number(s): "329457042"
Test #34:
score: 41
Accepted
time: 376ms
memory: 98916kb
input:
2821 2853
output:
81282690
result:
ok 1 number(s): "81282690"
Test #35:
score: 41
Accepted
time: 413ms
memory: 105984kb
input:
2875 2956
output:
105351485
result:
ok 1 number(s): "105351485"
Test #36:
score: 41
Accepted
time: 397ms
memory: 100804kb
input:
2879 2852
output:
672034506
result:
ok 1 number(s): "672034506"
Extra Test:
score: 0
Extra Test Passed