Submission #19791

#	Time	Username	Problem	Language	Result	Execution time	Memory
19791		tonyjjw	동전 (kriii4_E)	C++14	100 / 100	220 ms	8896 KiB

D

//*
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<vector>
#define all(A) (A).begin(), (A).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MN = 1000;
const ll mod = 1000000007;

int N;
ll D[MN][MN];

int main(){
	scanf("%d",&N);
	D[0][0]=1;
	D[1][0]=D[1][1]=1;
	for(int i=2;i<=N;i++)for(int j=0;j<MN;j++){
		if(i==j){
			D[i][j]++;
		}
		for(int k=0;k<i;k++){
			D[i][j]+=D[i-k-1][j^k];
			D[i][j]%=mod;
		}
	}
	printf("%lld\n",D[N][0]);
	return 0;
}
//*/

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