Submission #371328

#	Time	Username	Problem	Language	Result	Execution time	Memory
371328		peijar	Tents (JOI18_tents)	C++17	100 / 100	184 ms	70892 KiB

tents

#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]);
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52