PKU 3008 Push Botton Lock

http://acm.pku.edu.cn/JudgeOnline/problem?id=3088

• DP解法
• やり方が何通りかあるらしい
• ある押すボタンの集合について、それらのボタンを使ったシーケンスが何通り作れるかを計算していく
• 最後に全てのパターンを足して出力

ll solve(int B)
{
	static ll dp[1 << 11];
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;

	for (int from = 0; from < (1 << B); ++from) {
		for (int add = 1; add < (1 << B); ++add) {
			if (from & add) {
				continue;
			}

			dp[from | add] += dp[from];
		}
	}

	ll result = 0;
	for (int from = 1; from < (1 << B); ++from) {
		result += dp[from];
	}

	return result;
}

int main()
{
	ll answers[16];
	for (int i = 1; i <= 11; ++i) {
		answers[i] = solve(i);
	}

	int N;
	cin >> N;
	for (int testCase = 1; testCase <= N; ++testCase) {
		int B;
		cin >> B;
		cout << testCase << " " << B << " " << answers[B] << endl;
	}
}