This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
template<long long MOD>
class Num {
private:
long long expow(long long base, long long e) const {
long long ans = 1;
for (; e > 0; e/= 2) {
if (e % 2)
ans = ans * base % MOD;
base = base * base % MOD; }
return ans; }
public:
long long val;
Num(long long _val) {
val = _val % MOD;
val = val < 0 ? val + MOD : val; }
Num() : val(0) { }
inline Num operator + (const Num &arg) const {
Num res;
res.val = val + arg.val;
res.val = res.val >= MOD ? res.val - MOD : res.val;
return res; }
inline Num operator - (const Num &arg) const {
Num res;
res.val = val - arg.val;
res.val = res.val < 0 ? res.val + MOD : res.val;
return res; }
inline Num operator - () const {
Num res;
res.val = MOD - res.val;
res.val = res.val == MOD ? 0 : res.val;
return res; }
inline Num operator ^ (const int &arg) const {
return Num(expow(val, arg)); }
inline Num operator * (const Num &arg) const {
return Num(val * arg.val); }
inline Num operator / (const Num &arg) const {
return Num(val * expow(arg.val, MOD - 2)); }
inline void operator += (const Num &arg) {
(*this) = (*this) + arg; }
inline void operator -= (const Num &arg) {
(*this) = (*this) - arg; }
inline void operator *= (const Num &arg) {
(*this) = (*this) * arg; }
inline void operator /= (const Num &arg) {
(*this) = (*this) / arg; }
inline void operator ^= (const long long &arg) {
val = expow(val, arg); } };
template<long long MOD>
ostream &operator << (ostream &fo, const Num<MOD> &c) {
fo << c.val;
return fo; }
template<long long MOD>
istream &operator >> (istream &fi, Num<MOD> &c) {
fi >> c.val;
c = Num<MOD>(c.val);
return fi; }
const int N = 3005, MOD = 1e9 + 7;
Num<MOD> dp[N][N];
int n, m;
int main() {
#ifdef HOME
freopen("joi_tents.in", "r", stdin);
freopen("joi_tents.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
Num<MOD> ant;
cin >> n >> m;
for (int i = 0; i < N; ++i)
dp[0][i] = dp[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
dp[i][j]+= dp[i - 1][j];
if (j >= 2)
dp[i][j]+= dp[i - 1][j - 2] * (j * (j - 1) / 2);
if (i >= 2)
dp[i][j]+= dp[i - 2][j - 1] * (i - 1) * j;
dp[i][j]+= dp[i - 1][j - 1] * j * 4; }
cout << dp[n][m] - 1 << endl;
return 0; }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |