結果

提出番号	1449
提出者	square1001
言語	C++
提出日時	2018-08-04 12:21:18
問題名	(64)Or Plus Max 2
結果	MLE
点数	78%

---

テストケース

ソースコード

#include <map>
#include <vector>
#include <iostream>
using namespace std;
const int mod = 1000000007;
int N, K, D, P, comb[15][15];
map<vector<int>, bool> vis[44][825];
map<vector<int>, int> dp[44][825];
int solve(int dep, int sum, vector<int> v) {
	if (dep == N) return sum == K;
	if (vis[dep][sum][v]) return dp[dep][sum][v];
	int vs = 0, ret = 0;
	for (int i = (int)v.size() - 1; i >= -1; --i) {
		for (int j = 1; j <= D - vs; ++j) {
			vector<int> w(v.begin() + (i + 1), v.end());
			w.push_back(j);
			int mul = comb[D - vs][j] - (i >= 0 ? comb[D - vs - v[i]][j] : 0);
			int res = solve(dep + 1, sum + w.size(), w);
			ret = (ret + 1LL * mul * res) % mod;
		}
		if(i >= 0) vs += v[i];
	}
	vis[dep][sum][v] = true;
	dp[dep][sum][v] = ret;
	return ret;
}
int main() {
	cin >> N >> K >> P;
	while (1 << D < P) ++D;
	for (int i = 0; i <= D; ++i) {
		comb[i][0] = 1;
		for (int j = 1; j <= i; ++j) {
			comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
		}
	}
	int ret = solve(0, 0, vector<int>());
	cout << ret << '\n';
	return 0;
}