Submission #1325828

#TimeUsernameProblemLanguageResultExecution timeMemory
1325828csachy13NoM (RMI21_nom)C++20
100 / 100
70 ms55120 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 (ll i=1; i<=M; i++) num[i] = (2*N) / M + (i-1 < ((2*N) % M));
	for (ll i=0; i<=2015; i++) choose[i][i] = choose[i][0] = 1;
	for (ll i=1; i<=2015; i++)
		for (ll j=1; j<i; j++)
			choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % MOD;
	factorial[0] = twopow[0] = 1;
	for (ll 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 (ll group=0; group<M; group++) {
		ll changes = num[group + 1];
		for (ll full_pairs = 0; full_pairs<=N; full_pairs++) {
			if (dp[group][full_pairs] == 0) continue;
			if (stone_pairs_remaining[group][full_pairs] < full_pairs || stone_pairs_remaining[group][full_pairs] < 0) continue;
			for (ll i=0; i<=min(changes, (ll) full_pairs); i++) {
				ll one_pairs = stone_pairs_remaining[group][full_pairs] - full_pairs;
				if (changes - i < 0) continue;
				
				if (stone_pairs_remaining[group][full_pairs] - (changes - i) < 0) continue;
				
				stone_pairs_remaining[group + 1][full_pairs - i] = stone_pairs_remaining[group][full_pairs] - (changes - i);
				
				dp[group + 1][full_pairs - i] += 
						((
							(dp[group][full_pairs] * choose[full_pairs][i]) % MOD * 
							(choose[one_pairs][changes - i]) % MOD
						) % MOD 
						* factorial[changes]) % MOD;
				
				dp[group + 1][full_pairs - i] %= MOD;
			}
		}
	}
	
	cout << (dp[M][0] * twopow[N]) % 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...