| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 371328 |
2021-02-26T13:29:51 Z |
peijar |
Tents (JOI18_tents) |
C++17 |
|
184 ms |
70892 KB |
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;
using ll = long long;
template<typename... Args>
void read(Args&... args)
{
((cin >> args), ...);
}
template<typename T>
void read(vector<T> &vec)
{
for (auto &v : vec) read(v);
}
void write() {}
template<typename H, typename... T>
void write(const H &h, const T&... t)
{
cout << h;
if (sizeof...(t)) {cout << ' '; write(t...);}
}
template<typename T>
void write(const vector<T> &vec)
{
if (SZ(vec) == 0) return;
write(vec[0]);
for (int i(1); i < SZ(vec); ++i)
{cout << ' '; write(vec[i]);}
}
template<typename... Args>
void writeln(Args... args)
{
write(args...); cout << '\n';
}
template<const int32_t MOD>
struct ModInt {
long long x;
ModInt() : x(0) {}
ModInt(long long u) : x(u) { x %= MOD; if (x < 0) x += MOD;}
friend bool operator == (const ModInt& a, const ModInt& b) { return a.x == b.x; }
friend bool operator != (const ModInt& a, const ModInt& b) { return a.x != b.x; }
friend bool operator < (const ModInt& a, const ModInt& b) { return a.x < b.x; }
friend bool operator > (const ModInt& a, const ModInt& b) { return a.x > b.x; }
friend bool operator <= (const ModInt& a, const ModInt& b) { return a.x <= b.x; }
friend bool operator >= (const ModInt &a, const ModInt& b) { return a.x >= b.x; }
static ModInt sign(long long k) { return ((k & 1) ? ModInt(MOD-1) : ModInt(1)); }
ModInt& operator += (const ModInt& m) { x += m.x; if(x >= MOD) x -= MOD; return *this; }
ModInt& operator -= (const ModInt& m) { x -= m.x; if(x < 0LL) x += MOD; return *this; }
ModInt& operator *= (const ModInt& m) { x = (1LL * x * m.x) % MOD; return *this; }
friend ModInt operator - (const ModInt& a) { ModInt res(a); if(res.x) res.x = MOD - res.x; return res; }
friend ModInt operator + (const ModInt& a, const ModInt& b) { return ModInt(a) += ModInt(b); }
friend ModInt operator - (const ModInt& a, const ModInt& b) { return ModInt(a) -= ModInt(b); }
friend ModInt operator * (const ModInt& a, const ModInt& b) { return ModInt(a) *= ModInt(b); }
static long long fp(long long u, long long k) {
long long res = 1LL;
while(k > 0LL) {
if(k & 1LL) res = (res * u) % MOD;
u = (u * u) % MOD;
k /= 2LL;
}
return res;
}
static constexpr int mod() {return MOD;}
ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
ModInt inv() { return ModInt(fp(x, MOD-2)); }
ModInt& operator /= (const ModInt& m) { return *this *= ModInt(m).inv(); }
friend ModInt operator / (const ModInt& a, const ModInt& b) { return ModInt(a) *= ModInt(b).inv(); }
friend ostream& operator << (ostream& out, const ModInt& a) { return out << a.x; }
friend istream& operator >> (istream& in, ModInt& a) {return in >> a.x;}
};
const int MOD = 1e9 + 7;
using Mint = ModInt<MOD>;
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int nbLig, nbCol;
read(nbLig, nbCol);
vector<vector<Mint>> dp(nbLig+1, vector<Mint>(nbCol+1));
for (int col(0); col < nbCol; ++col)
dp[0][col] = 1;
for (ll ligRestante(1); ligRestante <= nbLig; ++ligRestante)
for (ll colRestante(0); colRestante <= nbCol; ++colRestante)
{
dp[ligRestante][colRestante] += dp[ligRestante-1][colRestante];
if (colRestante)
dp[ligRestante][colRestante] += 4*colRestante * dp[ligRestante-1][colRestante-1];
if (colRestante > 1)
dp[ligRestante][colRestante] += colRestante * (colRestante-1) / 2 * dp[ligRestante-1][colRestante-2];
if (ligRestante > 1 and colRestante > 0)
dp[ligRestante][colRestante] += colRestante * (ligRestante-1) * dp[ligRestante-2][colRestante-1];
}
writeln(dp[nbLig][nbCol]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
620 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
392 KB |
Output is correct |
| 10 |
Correct |
2 ms |
620 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
620 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
392 KB |
Output is correct |
| 10 |
Correct |
2 ms |
620 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
640 KB |
Output is correct |
| 15 |
Correct |
184 ms |
44296 KB |
Output is correct |
| 16 |
Correct |
9 ms |
3180 KB |
Output is correct |
| 17 |
Correct |
25 ms |
10092 KB |
Output is correct |
| 18 |
Correct |
35 ms |
12524 KB |
Output is correct |
| 19 |
Correct |
133 ms |
51536 KB |
Output is correct |
| 20 |
Correct |
103 ms |
41196 KB |
Output is correct |
| 21 |
Correct |
67 ms |
27244 KB |
Output is correct |
| 22 |
Correct |
65 ms |
27056 KB |
Output is correct |
| 23 |
Correct |
36 ms |
15104 KB |
Output is correct |
| 24 |
Correct |
175 ms |
70892 KB |
Output is correct |
| 25 |
Correct |
128 ms |
52716 KB |
Output is correct |
| 26 |
Correct |
147 ms |
60396 KB |
Output is correct |
| 27 |
Correct |
165 ms |
68204 KB |
Output is correct |
