結果

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

---

テストケース

ソースコード

#include <vector>
#include <iostream>
using namespace std;
const int mod = 1000000007;
int N, K, D, P, comb[15][15], dp[44][444][2052]; bool vis[44][444][2052];
int func(vector<int> v) {
	int ret = 0, s = 0;
	for (int i = 0; i < v.size(); ++i) {
		s += v[i];
		ret |= 1 << (s - 1);
	}
	ret |= 1 << s;
	return ret;
}
int solve(int dep, int sum, vector<int> v) {
	if (dep == N) return sum == K;
	int fv = func(v);
	if (vis[dep][sum][fv]) return dp[dep][sum][fv];
	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][fv] = true;
	dp[dep][sum][fv] = 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;
}