fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll int
  4. #define el "\n"
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define __ROOT__ int main()
  7. #pragma GCC optimize("O2")
  8. #define fi first
  9. #define se second
  10. #define MAXN 3001
  11. #define INF 1000000000000
  12. #define BLOCK_SIZE 425
  13. #define MAX_NODE 1001001
  14. #define LOG 19
  15. #define ALPHA_SIZE 26
  16. #define BASE 311
  17. #define NAME "check"
  18. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); // dùng để nén sort mảng compare
  19. using namespace std;
  20. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  21. const ll NMOD = 1;
  22. const int dx[] = {-1, 0, 1,0};
  23. const int dy[] = {0, 1, 0, -1};
  24. //**Variable**//
  25. string dp[MAXN][4][2] ; // ngay - vangmat - dimuon
  26. //**Struct**//
  27.  
  28. //**Function**//
  29. string add(string a  , string b ) {
  30. while(a.size() < b.size()) a = "0" + a ;
  31. while(b.size() < a.size()) b = "0" + b ;
  32. ll nho =0;
  33. string res;
  34. for(ll i = a.size() - 1;  i >= 0 ; i -- ) {
  35.     ll tong = nho + a[i]- '0' + b[i]-'0' ;
  36.     nho = tong /10 ;
  37.     res = to_string(tong % 10  )  + res ;
  38. }
  39. if(nho) res = "1" + res ;
  40. return res ;
  41. }
  42. string DP(ll pos , ll cnt , ll ok ) {
  43. string  &cur = dp[pos][cnt][ok] ;
  44. if(pos == 0){
  45.     return cur = "1" ;
  46. }
  47. if(cur != "-1" ) return cur ;
  48. cur = "0" ;
  49. if(cnt < 2) cur =add(cur, DP(pos -1 , cnt + 1 , ok ) ) ;// nghỉ
  50. if(!ok ) cur =add(cur,  DP(pos -1 , 0 , 1 )) ; // vắng
  51. cur =add(cur ,  DP(pos- 1 , 0 , ok ) )  ; //đi học
  52. return cur ;
  53. }
  54.  
  55. void init() {
  56.    for(ll i = 0 ; i < MAXN ; i ++ ) {
  57.     for(ll j = 0 ; j < 4 ; j ++ ) {
  58.         for(ll f = 0 ; f < 2 ; f ++ ) dp[i][j][f] = "-1" ;
  59.     }
  60.    }
  61. }
  62.  
  63. void solve() {
  64.     ll n ;
  65. while(cin >> n ){
  66. cout<< DP(n  , 0 , 0) << el  ;
  67. }
  68. }
  69.  
  70. __ROOT__ {
  71. //    freopen(NAME".inp" , "r" , stdin);
  72. //    freopen(NAME".out" , "w", stdout) ;
  73.     fast;
  74.     init();
  75.     solve();
  76. }
  77.  
Success #stdin #stdout 1.8s 8328KB
comments (?)
stdin
copy 
30
01
2009
3 
0
0
1
2
0
0
9
stdout
copy 
1918080160
3
6779831841412237463035262261781101899266869001002919482268696663387546400824286960816915589857139300395235011383928251040726316495435191524932750836857633327721954002401048507383961843585497959075953692573111088584931691789550281184990288770164787162404627792154866447227197280401692367380986439367857745521620447789922371686499627373115016360982559698489238371630254595059561740459983006945175585872041574776652331751739062565956264568754231655333843694434784990120106808775535801540394201558257526958607420196980009817678533564291845
19
1
1
3
8
1
1
1753
https://ideone.com/9nHngk
language:
C++14 (gcc 8.3)
created:
239 days ago
visibility:
secret

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!