fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define f1(i, n) for(int i=1;i<=n;++i)
  4. #define all(x) x.begin(), x.end()
  5. #define fi first
  6. #define se second
  7. #define mp make_pair
  8. #define pb push_back
  9. #define endl "\n"
  10. using namespace std;
  11. const int maxn = 1e5 + 5;
  12. const int MOD = 1e9 + 7;
  13.  
  14. int dp1[1005], dp2[1005][2], dp3[1005];
  15. int m, n;
  16. // dp1: từ chùa Thiên Trù đến Động Hương Tích
  17. // dp2: từ Động Hương Tích xuống lưng chừng núi Lão
  18. // dp3: từ lưng chừng núi Lão lên chùa Thiên Trù
  19. // dp3[i][j] = số cách đi đến bậc thứ i mà còn j lần nhảy 3 bước
  20. // ans = dp1[m+n] * dp2[]
  21.  
  22. void solve(int m, int n) {
  23.     // Kích thước tối đa cần tính
  24.     int max_steps = max(m, n);
  25.  
  26.     // ---- Tính dp1, dp3, và dp2[...][1] (vì dp3 và dp2[...][1] giống hệt nhau) ----
  27.     dp1[0] = 1; dp1[1] = 1; dp1[2] = 2; dp1[3] = 4;
  28.     dp3[0] = 1; dp3[1] = 1; dp3[2] = 2;
  29.  
  30.     for (int i = 3; i <= max_steps; ++i) {
  31.         // dp1 (bước 1, 2, 3)
  32.         if (i <= max_steps) // Chỉ tính dp1 nếu cần
  33.             dp1[i] = (dp1[i - 1] + dp1[i - 2] + dp1[i - 3]) % MOD;
  34.     }
  35.     for (int i = 2; i <= max_steps; ++i) {
  36.         // dp3 (bước 1, 2)
  37.         if (i <= max_steps) // Chỉ tính dp3 nếu cần
  38.             dp3[i] = (dp3[i - 1] + dp3[i - 2]) % MOD;
  39.     }
  40.  
  41.     // ---- Tính dp2[...][0] (Phần 2: N bậc, {1, 2} + 1x{3}) ----
  42.     // dp2[i][1] (chưa dùng bước 3) chính là dp3[i]
  43.     // dp2[i][0] (đã dùng 1 bước 3)
  44.  
  45.     // Khởi tạo mảng dp2
  46.     for (int i = 0; i <= n; ++i) {
  47.         dp2[i][0] = 0;
  48.         dp2[i][1] = dp3[i]; // Tận dụng dp3 đã tính
  49.     }
  50.  
  51.     // Cơ sở: dp2[0][1] = 1, dp2[0][0] = 0 (đã được gán từ dp3[0])
  52.  
  53.     for (int i = 1; i <= n; ++i) {
  54.         // 1. Tính dp2[i][1] (đã được tính ở trên)
  55.  
  56.         // 2. Tính dp2[i][0] (đã dùng 1 bước 3)
  57.         // a) Bước 1 từ (i-1) (vốn đã dùng bước 3)
  58.         if (i - 1 >= 0) dp2[i][0] = (dp2[i][0] + dp2[i - 1][0]) % MOD;
  59.         // b) Bước 2 từ (i-2) (vốn đã dùng bước 3)
  60.         if (i - 2 >= 0) dp2[i][0] = (dp2[i][0] + dp2[i - 2][0]) % MOD;
  61.         // c) Bước 3 từ (i-3) (vốn CHƯA dùng bước 3) -> dùng bước 3 tại đây
  62.         if (i - 3 >= 0) dp2[i][0] = (dp2[i][0] + dp2[i - 3][1]) % MOD;
  63.     }
  64.  
  65.     // ---- Phần 3: 1 -> m (bước 1, 2) ----
  66.     // Đã được tính trong dp3[m]
  67.  
  68.     // ---- Tính kết quả ----
  69.     // res1 = (Phần 1a: M bậc, {1,2,3}) * (Phần 1b: N bậc, {1,2,3})
  70.     int res1 = (dp1[m] * dp1[n]) % MOD;
  71.     // res2 = (Phần 2: N bậc, {1,2} + 1x{3})
  72.     int res2 = dp2[n][0];
  73.     // res3 = (Phần 3: M bậc, {1,2})
  74.     int res3 = dp3[m];
  75.  
  76.     // Nhân và mod cẩn thận
  77.     int ans = (res1 * res2) % MOD;
  78.     ans = (ans * res3) % MOD;
  79.  
  80.     cout << ans << endl;
  81.  
  82. }
  83.  
  84. main() {
  85.     ios::sync_with_stdio(false);
  86.     cin.tie(nullptr);
  87.  
  88.     // freopen("ATRISET.INP", "r", stdin);
  89.     // freopen("ATRISET.OUT", "w", stdout);
  90.  
  91.     while (cin >> m >> n) {
  92.         solve(m, n);
  93.     }
  94.  
  95.  
  96. }
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cKY5AS
language:
C++14 (gcc 8.3)
created:
16 days 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!