이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 3e3 + 5, mod = 1e9 + 7;
inline void sadd(int& x, int y){
if ((x += y) >= mod) x -= mod;
return;
}
inline int add(int x, int y){
if ((x += y) >= mod) x -= mod;
return x;
}
inline void ssub(int& x, int y){
if ((x -= y) < 0) x += mod;
return;
}
inline int sub(int x, int y){
if ((x -= y) < 0) x += mod;
return x;
}
inline int mul(int x, int y){
return 1ll * x * y % mod;
}
inline int binpow(int x, int y){
int ans = 1;
while (y){
if (y & 1) ans = mul(ans, x);
x = mul(x, x);
y >>= 1;
}
return ans;
}
inline int inv(int x){
return binpow(x, mod - 2);
}
#define div __div__
inline int div(int x, int y){
return mul(x, binpow(y, mod - 2));
}
int fac[N], invfac[N];
void calfac(){
fac[0] = invfac[0] = 1;
For(i, 1, N){
fac[i] = mul(fac[i - 1], i);
}
invfac[N - 1] = binpow(fac[N - 1], mod - 2);
FordE(i, N - 2, 1){
invfac[i] = mul(invfac[i + 1], i + 1);
}
}
inline int C(int n, int k){
if (n < 0 or k < 0 or k > n){
return 0;
}
return mul(fac[n], mul(invfac[k], invfac[n - k]));
}
inline int P(int n, int k){
if (n < 0 or k < 0 or k > n){
return 0;
}
return mul(fac[n], invfac[n - k]);
}
int n, m;
int dp[N][N];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
calfac();
cin >> n >> m;
ForE(j, 0, m){
dp[0][j] = 1;
}
ForE(i, 1, n){
ForE(j, 0, m){
dp[i][j] = dp[i - 1][j];
if (j >= 1){
sadd(dp[i][j], mul(dp[i - 1][j - 1], 4 * j));
}
if (j >= 2){
sadd(dp[i][j], mul(dp[i - 1][j - 2], j * (j - 1) / 2));
}
if (i >= 2 and j >= 1){
sadd(dp[i][j], mul(dp[i - 2][j - 1], (i - 1) * j));
}
}
}
cout << sub(dp[n][m], 1) << endl;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |