Submission #19854

#	Time	Username	Problem	Language	Result	Execution time	Memory
19854		Qwaz	동전 (kriii4_E)	C++98	100 / 100	43 ms	2232 KiB

D

#include <iostream>
#include <vector>
using namespace std;

const int mod = 1000000007;

// dp[last][xor]
int dp[256][256] = {0}, ndp[256][256];
inline void add_to(int &a, int b) {
	a = (a + b) % mod;
}

int main() {
	int n;
	cin >> n;

	dp[0][0] = 1;
	for (int l = 0; l < n; l++) {
		for (int i = 0; i <= l + 1; i++)
			for (int j = 0; j <= l + 1; j++)
				ndp[i][j] = 0;
		for (int i = 0; i <= l; i++)
			for (int j = 0; j <= l; j++) {
				// not flipped
				add_to(ndp[i + 1][j ^ i ^ (i + 1)], dp[i][j]);
				// flipped
				add_to(ndp[0][j], dp[i][j]);
			}
		for (int i = 0; i <= l + 1; i++)
			for (int j = 0; j <= l + 1; j++)
				dp[i][j] = ndp[i][j];
	}

	int sum = 0;
	for (int i = 0; i <= n; i++)
		add_to(sum, dp[i][0]);

	cout << sum << endl;

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95