Submission #19795

#	Time	Username	Problem	Language	Result	Execution time	Memory
19795		cki86201	동전 (kriii4_E)	C++14	100 / 100	64 ms	65224 KiB

D

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

const ll MOD = 1e9 + 7;

ll pw(ll x, ll y){
	ll res = 1;
	while(y){
		if(y & 1)res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}

int d[252][256][252];

int dfs(int r, int bit, int nw){
	if(d[r][bit][nw] != -1)return d[r][bit][nw];
	if(r == 0)return (bit^nw) == 0;
	return d[r][bit][nw] = (dfs(r-1, bit ^ (nw), 0) + dfs(r-1, bit, nw+1)) % MOD;
}

int main(){
	int n;
	scanf("%d", &n);
	memset(d, -1, sizeof d);
	printf("%d", dfs(n, 0, 0));
	return 0;
}

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