repl.it
@AllenLi1/

Trains

C++11

No description

fork
loading
Files
  • main.cpp
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main(int argc, const char * argv[]) {
  int n;
  cin >> n;
  long long fs[] = {0};
  fs[0] = 1;
  fs[1] = 1;
  fs[2] = 2;
  for (int i = 3; i <= n; i++) {
    for (int j = 0; j < i; j++) {
      fs[i] += (fs[j]*fs[i-j-1]) % 100000000;
    }
    fs[i] %= 100000000;
  }
  cout << fs[n];
}
Fetching token
?