Submission #1325822

#TimeUsernameProblemLanguageResultExecution timeMemory
1325822csachy13NoM (RMI21_nom)C++20
9 / 100
12 ms23844 KiB
#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;
using ll = long long;
using ld = long double;

ll dp[2015][2015]; // this is 1-INDEXED for M
ll stone_pairs_remaining[2015][2015];
ll choose[2016][2016];
ll twopow[2016], factorial[2016];
ll num[2015]; // this is 1-INDEXED for M

int main() {
	// cin.tie(0); ios_base::sync_with_stdio(0);
	
	ll N, M;
	cin >> N >> M;
	
	// PRECOMPUTATION
	for (int i=1; i<=M; i++) num[i] = (2*N) / M + (i-1 < ((2*N) % M));
	for (int i=0; i<=2015; i++) choose[i][i] = choose[i][0] = 1;
	for (int i=1; i<=2015; i++)
		for (int j=1; j<i; j++)
			choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % MOD;
	factorial[0] = twopow[0] = 1;
	for (int i=1; i<=2015; i++) 
		factorial[i] = (factorial[i - 1] * i) % MOD, twopow[i] = (twopow[i - 1] << 1) % MOD;
	choose[0][0] = 1;
	///////////
	
	dp[0][N] = 1; stone_pairs_remaining[0][N] = N;
	
	for (int group=0; group<M; group++) {
		// cout << "GROUP " << group << '\n';
		for (int full_pairs = 0; full_pairs<=N; full_pairs++) {
			// cout << dp[group][full_pairs] << ' ' << stone_pairs_remaining[group][full_pairs];
			for (int i=0; i<=num[group + 1]; i++) {
				if (full_pairs - i < 0) continue;
				ll one_pairs = stone_pairs_remaining[group][full_pairs] - full_pairs;
				if (one_pairs < 0) continue;
				if (num[group + 1] - i < 0) continue;
				if (stone_pairs_remaining[group][full_pairs] - (num[group + 1] - i) < 0) continue;
				dp[group + 1][full_pairs - i] += ((dp[group][full_pairs] * choose[full_pairs][i]) % MOD * (twopow[i] * choose[one_pairs][num[group + 1] - i]) % MOD) % MOD * factorial[num[group + 1]];
				dp[group + 1][full_pairs - i] %= MOD;
				// cout << "\t " << i << " " << dp[group][full_pairs] * choose[full_pairs][i] * twopow[i] * choose[one_pairs][num[group] - i] * factorial[num[group]] << '\n';
				stone_pairs_remaining[group + 1][full_pairs - i] = stone_pairs_remaining[group][full_pairs] - (num[group + 1] - i);
			}
			// cout << '\n';
		}
	}
	
	cout << dp[M][0] % MOD << '\n';
	
	
	
	
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...