fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5. using namespace std;
  6. int n;
  7. int DP[101][10],MOD = 1000000000;
  8. int dp(int i, int j) {
  9.   if (i == 0) return 0;
  10.   if (i < 0 || j < 0 || j > 9) return 0;
  11.   if (i == 1 && j == 0) return 0;
  12.   if (i == 1 && j > 0)  return 1;
  13.   if (DP[i][j] == 0) DP[i][j] = (dp(i-1, j-1) + dp(i-1, j+1))%MOD;
  14.   return DP[i][j];
  15. }
  16. int main() {
  17.   scanf("%d", &n);
  18.   long long s = 0;
  19.   for (int j = 0; j < 10; j++) s += dp(n, j);
  20.   printf("%lld\n", s%MOD);
  21.   return 0;
  22. }
  23.  
  24.  
  25. //출처: http://b...content-available-to-author-only...m.com/53 [I'm programmer]
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
3
stdout
copy 
32
https://ideone.com/K3RyHp
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!