QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#829113 | #8728. Tablica | fractal | 100 ✓ | 75ms | 123772kb | C++17 | 4.5kb | 2024-12-24 03:04:36 | 2024-12-24 03:04:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 3e3 + 200;
const int M = 1e6;
const int inf = 2e9 + 3;
const ll INF = 1e18;
template<int mod>
class Modular {
public:
int val;
Modular() : val(0) {}
Modular(int new_val) : val(new_val) {}
// Modular(long long new_val) : val(new_val % mod) {} // AFFECTS OPERATOR* (because it has one more %)
friend Modular operator+(const Modular& a, const Modular& b) {
if (a.val + b.val >= mod) return a.val + b.val - mod;
else return a.val + b.val;
}
friend Modular operator-(const Modular& a, const Modular& b) {
if (a.val - b.val < 0) return a.val - b.val + mod;
else return a.val - b.val;
}
friend Modular operator*(const Modular& a, const Modular& b) {
return 1ll * a.val * b.val % mod;
}
friend Modular binpow(Modular a, long long n) {
Modular res = 1;
for (; n; n >>= 1) {
if (n & 1) res *= a;
a *= a;
}
return res;
}
/*
friend Modular inv(const Modular& a) {
Modular x, y;
gcd(a.val, mod, x, y);
return x;
}
*/
friend Modular inv(const Modular& a) {
return binpow(a, mod - 2);
}
friend Modular operator^(const Modular& a, const long long& b) {
if (b >= 0)
return binpow(a, b % (mod - 1));
return binpow(inv(a), (-b) % (mod - 1));
}
/* ALTERNATIVE INVERSE FUNCTION USING EXTENDED EUCLIDEAN ALGORITHM
friend void gcd(int a, int b, Modular& x, Modular& y) {
if (a == 0) {
x = Modular(0);
y = Modular(1);
return;
}
Modular x1, y1;
gcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
}
*/
Modular operator/(const Modular& ot) const {
return *this * inv(ot);
}
Modular& operator++() {
if (val + 1 == mod) val = 0;
else ++val;
return *this;
}
Modular operator++(int) {
Modular tmp = *this;
++(*this);
return tmp;
}
Modular operator+() const {
return *this;
}
Modular operator-() const {
return 0 - *this;
}
Modular& operator+=(const Modular& ot) {
return *this = *this + ot;
}
Modular& operator-=(const Modular& ot) {
return *this = *this - ot;
}
Modular& operator*=(const Modular& ot) {
return *this = *this * ot;
}
Modular& operator/=(const Modular& ot) {
return *this = *this / ot;
}
bool operator==(const Modular& ot) const {
return val == ot.val;
}
bool operator!=(const Modular& ot) const {
return val != ot.val;
}
bool operator<(const Modular& ot) const {
return val < ot.val;
}
bool operator>(const Modular& ot) const {
return val > ot.val;
}
explicit operator int() const {
return val;
}
};
template<int mod>
istream& operator>>(istream& istr, Modular<mod>& x) {
return istr >> x.val;
}
template<int mod>
ostream& operator<<(ostream& ostr, const Modular<mod>& x) {
return ostr << x.val;
}
const int mod = 1e9 + 7;
using Mint = Modular<mod>;
int a, b;
Mint g[N][N], P[N][N], G[N][N];
int main() {
cin.tie(0)->sync_with_stdio(0);
g[0][0] = 1;
P[0][0] = 1;
G[0][0] = 1;
cin >> a >> b;
for (int n = 1; n <= a; ++n) {
Mint ii2 = Mint(1)/2;
Mint iin = Mint(1)/n;
for (int m = 1; m <= b; ++m) {
if (n >= 2) g[n][m] += P[n-2][m-1] + G[n-2][m-1];
if (m >= 2) g[n][m] += P[n-1][m-2];
if (n >= 2 && m >= 2) g[n][m] += G[n-2][m-2];
g[n][m] *= ii2;
g[n][m] += P[n-1][m-1];
g[n][m] *= iin;
G[n][m] = G[n-1][m-1] + g[n][m];
P[n][m] = P[n-1][m-1] + G[n][m];
}
}
Mint ans = g[a][b];
for (int i = 1; i <= a; ++i) ans = ans * i;
for (int i = 1; i <= b; ++i) ans = ans * i;
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 12ms
memory: 123644kb
input:
5 6
output:
456750
result:
ok 1 number(s): "456750"
Test #2:
score: 10
Accepted
time: 8ms
memory: 123772kb
input:
6 6
output:
5464710
result:
ok 1 number(s): "5464710"
Test #3:
score: 10
Accepted
time: 3ms
memory: 123768kb
input:
3 5
output:
270
result:
ok 1 number(s): "270"
Test #4:
score: 10
Accepted
time: 0ms
memory: 123640kb
input:
3 6
output:
90
result:
ok 1 number(s): "90"
Test #5:
score: 10
Accepted
time: 0ms
memory: 123644kb
input:
4 6
output:
14580
result:
ok 1 number(s): "14580"
Test #6:
score: 10
Accepted
time: 12ms
memory: 123652kb
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: 8ms
memory: 123612kb
input:
50 49
output:
750700714
result:
ok 1 number(s): "750700714"
Test #8:
score: 18
Accepted
time: 3ms
memory: 123704kb
input:
50 50
output:
630532893
result:
ok 1 number(s): "630532893"
Test #9:
score: 18
Accepted
time: 7ms
memory: 123720kb
input:
41 34
output:
800856205
result:
ok 1 number(s): "800856205"
Test #10:
score: 18
Accepted
time: 7ms
memory: 123624kb
input:
39 41
output:
541550932
result:
ok 1 number(s): "541550932"
Test #11:
score: 18
Accepted
time: 4ms
memory: 123644kb
input:
38 46
output:
651393374
result:
ok 1 number(s): "651393374"
Test #12:
score: 18
Accepted
time: 0ms
memory: 123644kb
input:
37 39
output:
746919932
result:
ok 1 number(s): "746919932"
Test #13:
score: 18
Accepted
time: 8ms
memory: 123716kb
input:
30 50
output:
214086425
result:
ok 1 number(s): "214086425"
Test #14:
score: 18
Accepted
time: 8ms
memory: 123648kb
input:
50 41
output:
193351204
result:
ok 1 number(s): "193351204"
Test #15:
score: 18
Accepted
time: 3ms
memory: 123704kb
input:
44 32
output:
63855946
result:
ok 1 number(s): "63855946"
Test #16:
score: 18
Accepted
time: 16ms
memory: 123768kb
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: 123704kb
input:
199 200
output:
841552647
result:
ok 1 number(s): "841552647"
Test #18:
score: 31
Accepted
time: 0ms
memory: 123588kb
input:
200 200
output:
157842226
result:
ok 1 number(s): "157842226"
Test #19:
score: 31
Accepted
time: 7ms
memory: 123724kb
input:
156 199
output:
216453917
result:
ok 1 number(s): "216453917"
Test #20:
score: 31
Accepted
time: 3ms
memory: 123576kb
input:
161 199
output:
539960909
result:
ok 1 number(s): "539960909"
Test #21:
score: 31
Accepted
time: 3ms
memory: 123572kb
input:
194 160
output:
764024671
result:
ok 1 number(s): "764024671"
Test #22:
score: 31
Accepted
time: 7ms
memory: 123640kb
input:
184 195
output:
117763744
result:
ok 1 number(s): "117763744"
Test #23:
score: 31
Accepted
time: 4ms
memory: 123624kb
input:
152 174
output:
350941677
result:
ok 1 number(s): "350941677"
Test #24:
score: 31
Accepted
time: 3ms
memory: 123640kb
input:
195 186
output:
130526660
result:
ok 1 number(s): "130526660"
Test #25:
score: 31
Accepted
time: 3ms
memory: 123704kb
input:
173 159
output:
754934766
result:
ok 1 number(s): "754934766"
Test #26:
score: 31
Accepted
time: 3ms
memory: 123584kb
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: 75ms
memory: 123644kb
input:
3000 2999
output:
5195706
result:
ok 1 number(s): "5195706"
Test #28:
score: 41
Accepted
time: 75ms
memory: 123720kb
input:
3000 3000
output:
224347336
result:
ok 1 number(s): "224347336"
Test #29:
score: 41
Accepted
time: 62ms
memory: 123704kb
input:
2854 2864
output:
513408195
result:
ok 1 number(s): "513408195"
Test #30:
score: 41
Accepted
time: 65ms
memory: 123624kb
input:
2887 2803
output:
58832696
result:
ok 1 number(s): "58832696"
Test #31:
score: 41
Accepted
time: 68ms
memory: 123772kb
input:
2800 2925
output:
804387597
result:
ok 1 number(s): "804387597"
Test #32:
score: 41
Accepted
time: 58ms
memory: 123584kb
input:
2842 2813
output:
971828715
result:
ok 1 number(s): "971828715"
Test #33:
score: 41
Accepted
time: 72ms
memory: 123648kb
input:
2808 2972
output:
329457042
result:
ok 1 number(s): "329457042"
Test #34:
score: 41
Accepted
time: 65ms
memory: 123644kb
input:
2821 2853
output:
81282690
result:
ok 1 number(s): "81282690"
Test #35:
score: 41
Accepted
time: 70ms
memory: 123704kb
input:
2875 2956
output:
105351485
result:
ok 1 number(s): "105351485"
Test #36:
score: 41
Accepted
time: 63ms
memory: 123716kb
input:
2879 2852
output:
672034506
result:
ok 1 number(s): "672034506"
Extra Test:
score: 0
Extra Test Passed