Submission #20237

#	Time	Username	Problem	Language	Result	Execution time	Memory
20237		sui	동전 (kriii4_E)	C++14	100 / 100	49 ms	1 KiB

D

#define _CRT_SECURE_NO_WARNINGS // scanf(), gets() (needed for Visual C++)

#include <cassert>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>

using namespace std;

#define MEMSET(x, WITH) memset(x, (WITH), sizeof(x))
#define FOR(i, E) for (int i=0; i<(E); i++)

typedef long long ll;
const ll MOD = 1000000007;
//const double PI = atan(1) * 4;










const int BIT = 1<<8;

int N;
ll dp[253][2][BIT];

int main() {
	cin >> N;

	dp[0][0][0] = 1;

	dp[1][0][0] = 1;
	dp[1][1][1] = 1;
	
	for (int n=2; n<=N; n++) {
		FOR(x, BIT) dp[n][0][x] = (dp[n-1][0][x] + dp[n-1][1][x]) % MOD;

		FOR(x, BIT) for (int t=1; t<=n; t++)
			dp[n][1][x] += dp[n-t][0][x^t],
			dp[n][1][x] %= MOD;
	}


	ll ans = (dp[N][0][0] + dp[N][1][0]) % MOD;
	cout << ans << endl;

	return 0;
}

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