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 <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 2e3 + 10, maxm = 1e7 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;
int is[maxn];
ll fact[maxn * 2];
ll dp[maxn][maxn];
ll bp(ll a, ll n){
ll res = 1;
while (n > 0){
if (n & 1)
res *= a;
a *= a, n >>= 1;
res %= mod, a %= mod;
}
return res;
}
ll cnk(int n, int k){
return fact[n] * bp(fact[k], mod - 2) % mod * bp(fact[n - k], mod - 2) % mod;
}
int n, m;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("paths.in", "r", stdin);
// freopen("paths.out", "w", stdout);
cin >> n >> m;
fact[0] = 1;
for (int i = 1; i <= n * 2; ++i){
fact[i] = fact[i - 1] * i % mod;
int z = i % m + 1;
is[z] += 1;
}
dp[0][0] = 1;
for (int i = 1; i <= m; ++i){
for (int j = 0; j <= n; ++j){
if (dp[i - 1][j] > 0){
for (int k = 0; k * 2 <= is[i]; ++k){
if (j + k <= n){
dp[i][j + k] = (dp[i][j + k] + dp[i - 1][j] * cnk(j + k, k) % mod * fact[is[i]] % mod * bp(fact[is[i] - 2 * k], mod - 2) % mod) % mod;
}
}
}
}
}
ll ans = fact[2 * n];
int cur = 1;
//cout << ans << '\n';
for (int i = 1; i <= n; ++i){
ll del = cur * cnk(n, i) % mod * fact[2 * n - 2 * i] % mod * dp[m][i] % mod;
cur *= -1;
ans = (ans - del + mod) % mod;
}
cout << ans;
}
/*
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |