Submission #509626

#	Time	Username	Problem	Language	Result	Execution time	Memory
509626		minhcool	NoM (RMI21_nom)	C++17	100 / 100	137 ms	23088 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2005;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, dp[N][N], pw2[N << 2];

int fac[N << 2], inv[N << 2];

int binpw(int base, int pw){
	int ans = 1;
	while(pw){
		if(pw & 1) ans = (ans * base) % mod;
		base = (base * base) % mod;
		pw >>= 1;
	}
	return ans;
}

void prep(){
	fac[0] = 1;
	for(int i = 1; i <= 8000; i++) fac[i] = (fac[i - 1] * i) % mod;
	for(int i = 0; i <= 8000; i++) inv[i] = binpw(fac[i], mod - 2);
	pw2[0] = 1;
	for(int i = 1; i <= 8000; i++) pw2[i] = (pw2[i - 1] * 2) % mod;
}

int c(int n, int k){
	if(k < 0 || n < k) return 0;
	int temp = (fac[n] * inv[k]) % mod;
	return (temp * inv[n - k]) % mod;
}

void add(int &a, int b){
	a = (a + b) % mod;
}

void process(){
	prep();
	cin >> n >> m;
	dp[0][n] = 1;
	int tol = 0;
	for(int i = 1; i <= m; i++){
		int mx = (2 * n) / m;
		if(((2 * n) % m) >= i) mx++;
		tol += mx;
		for(int two = 0; two <= n; two++){
			int one = (n - two) * 2 - tol;
			if(one < 0) break;
			for(int two2 = two; two2 <= min(n, two + mx); two2++){
				int one2 = (mx - two2 + two);
				int temp = c(two2, two2 - two) * c(one + one2 - (two2 - two), one2);
				temp %= mod;
				temp = (temp * fac[mx]) % mod;
				//cout << temp << "\n";
				temp = (temp * pw2[two2 - two]) % mod;
				//cout << two2 << " " << temp << "\n";
				add(dp[i][two], temp * dp[i - 1][two2]);
			}
			//cout << i << " " << two << " " << dp[i][two] << "\n";
		}
	}
	cout << dp[m][0] << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

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