Submission #509533

#	Time	Username	Problem	Language	Result	Execution time	Memory
509533		hohohaha	NoM (RMI21_nom)	C++14	100 / 100	144 ms	39620 KiB

Main

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define forIT(it, begin, end) for(__typeof(end) it = (begin) - ((begin) > (end)); it != (end) - ((begin) > (end)); it += 1 - 2 * ((begin) > (end)) )

void solve();

signed main() {
//	freopen("test.inp", "r", stdin); 
//   fastio();
   int tc = 1;
//   cin >> tc; 
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;
const int maxn = 4000 + 5, inf = LLONG_MAX / 100ll, mod = 1e9 + 7;

int n, m; 
int fac[maxn]; 
int inv_fac[maxn]; 
int bp(int i, int p) { 	
	int r = 1;
	while(p) { 
		if(p & 1) r = r * i % mod; 
		i = i * i % mod; 
		p >>= 1; 
	}
	return r; 
}
int C(int n, int k) { 
	if(k < 0 or k > n) return 0; 
	return fac[n] * inv_fac[n - k] % mod * inv_fac[k] % mod;
}
int dp[maxn][maxn]; 
int w[maxn]; 
void solve() {	
	cin >> n >> m; 
	fac[0] = inv_fac[0] = 1; 
	fori(i,1,2 * n) { 
	 	fac[i] = fac[i - 1] * i % mod; 
	 	inv_fac[i] = bp(fac[i], mod -2); 
	 }
	fori(i, 0, m - 1) { 	
		int num = 2 * n / m + (i < 2 * n % m);  
//		cout << i << sp << num << sp << endl; 
	 	fori(used, 0, n) { 
	 	 	fori(tran, 0, num / 2) { 
	 	 		(dp[i][used + tran] += (i? dp[i - 1][used]: used == 0) * C(tran + used, tran) % mod * fac[num] % mod * inv_fac[num - 2 * tran] % mod) %= mod;  
	 	 	}
	 	 }
//	 	fori(used, 0, n) { 
//	 	 	cout << i << sp << used << sp << dp[i][used] << endl; 
//	 	 }
	 }
//	 cout << C(2, 1) << endl; 
	 int ans = 0; 
	 fori(i, 0, n) { 
	  	w[i] = dp[m - 1][i] * fac[2 * n - 2 * i] % mod; //cout << i << sp << w[i] << endl; 
	  	(ans += w[i] * C(n, i) * bp(-1, i) % mod) %= mod; 
	  }
	  if(ans < 0) ans += mod;
	cout << ans; 

}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48