Submission #19869

#	Time	Username	Problem	Language	Result	Execution time	Memory
19869		xdoju	동전 (kriii4_E)	C++14	100 / 100	30 ms	1348 KiB

D

#include <stdio.h>

const int MOD = 1000000007;

int dp[260][260];

int main(){
  int N; scanf("%d", &N);

  dp[0][0] = 1;

  for(int i = 1; i <= N; i++){
    for(int j = 0; j < i; j++){ // number of 1
      for(int k = 0; k < 256; k++){
        dp[i][j ^ k] += dp[i - j - 1][k];
        dp[i][j ^ k] %= MOD;
      }
    }
    for(int k = 0; k < 256; k++){
      dp[i][i ^ k] += dp[0][k];
      dp[i][i ^ k] %= MOD;
    }
  }

  printf("%d\n", dp[N][0]);
  return 0;
}

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