Submission #19977

#	Time	Username	Problem	Language	Result	Execution time	Memory
19977		sui	동전 (kriii4_E)	C++14	100 / 100	54 ms	2728 KiB

D

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

//#define NDEBUG
#include <cassert>

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

#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <deque>

using namespace std;

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

#define GETINT(x) scanf("%d", &x)
#define GETDBL(x) scanf("%lf", &x)
#define GETSTR(x) scanf("%s", x)
#define NEWINT(x) int x; scanf("%d", &x)
#define NEWDBL(x) double x; scanf("%lf", &x)
#define NEWLN putchar('\n')

#ifdef _WIN32
#define popcnt __popcnt
#else
#define popcnt __builtin_popcount
#endif

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




int N;




ll dp[253][2][256];


int main() {
	cin >> N;


	/*
	ll pow2[253];
	pow2[0] = 1;
	for (int i=1; i<=N; i++) pow2[i] = pow2[i-1] * 2 % MOD;
	*/



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


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

	for (int i=1; i<=N; i++) {

		for (int firstStep=1; firstStep<=i; firstStep++) {
			for (int s=0; s<256; s++) {
				dp[i][1][firstStep^s] += dp[i-firstStep][0][s];
				dp[i][1][firstStep^s] %= MOD;

				dp[i][0][s] += dp[i-firstStep][1][s];
				dp[i][0][s] %= MOD;
			}
		}

	}





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


	return 0;
}

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