fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int MOD = 1000000007;
  9. const int MAX_N = 15; // Giới hạn an toàn cho Bitmask DP là n <= 12
  10.  
  11. vector<vector<int>> INDEP;
  12. long long memoH[MAX_N + 1];
  13. long long memoF[MAX_N + 1][MAX_N + 1];
  14. long long memoR[MAX_N + 1][MAX_N + 1];
  15.  
  16. // Tính lũy thừa a^b % MOD
  17. long long power(long long base, long long exp) {
  18.     long long res = 1;
  19.     base %= MOD;
  20.     while (exp > 0) {
  21.         if (exp % 2 == 1) res = (res * base) % MOD;
  22.         base = (base * base) % MOD;
  23.         exp /= 2;
  24.     }
  25.     return res;
  26. }
  27.  
  28. // Khởi tạo các trạng thái Bitmask (Tập độc lập) không có 2 bit 1 kề nhau
  29. void precompute_indep(int n) {
  30.     int max_L = 2 * n - 1;
  31.     if (max_L < 0) max_L = 0;
  32.     INDEP.assign(max_L + 1, vector<int>());
  33.  
  34.     for (int L = 0; L <= max_L; ++L) {
  35.         int max_mask = 1 << L;
  36.         for (int m = 0; m < max_mask; ++m) {
  37.             if ((m & (m << 1)) == 0) {
  38.                 INDEP[L].push_back(m);
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. // SOS DP: Sum Over Subsets (Zeta Transform)
  45. void subset_sums(vector<int>& out, int L) {
  46.     int size = 1 << L;
  47.     for (int i = 0; i < L; ++i) {
  48.         int step = 1 << i;
  49.         int block = step << 1;
  50.         for (int start = 0; start < size; start += block) {
  51.             int mid = start + step;
  52.             int end = start + block;
  53.             for (int m = mid; m < end; ++m) {
  54.                 int s = out[m] + out[m - step];
  55.                 out[m] = (s >= MOD) ? (s - MOD) : s;
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. // Hàm đếm số cách xếp Lục giác (Tập độc lập) trên lưới DP
  62. int count_independent_sets(const vector<int>& row_lengths) {
  63.     if (row_lengths.empty()) return 1;
  64.  
  65.     int L0 = row_lengths[0];
  66.     vector<int> dp(1 << L0, 0);
  67.     for (int m : INDEP[L0]) {
  68.         dp[m] = 1;
  69.     }
  70.  
  71.     for (size_t i = 1; i < row_lengths.size(); ++i) {
  72.         int Lc = row_lengths[i - 1];
  73.         int Ln = row_lengths[i];
  74.  
  75.         vector<int> subs = dp;
  76.         subset_sums(subs, Lc); // Biến đổi SOS DP
  77.  
  78.         vector<int> dp2(1 << Ln, 0);
  79.         int fullmask = (1 << Lc) - 1;
  80.  
  81.         if (Ln == Lc + 1) {
  82.             for (int b : INDEP[Ln]) {
  83.                 int forb = (b | (b >> 1)) & fullmask;
  84.                 int allowed = fullmask ^ forb;
  85.                 dp2[b] = subs[allowed];
  86.             }
  87.         } else if (Ln == Lc - 1) {
  88.             for (int b : INDEP[Ln]) {
  89.                 int forb = (b | (b << 1)) & fullmask;
  90.                 int allowed = fullmask ^ forb;
  91.                 dp2[b] = subs[allowed];
  92.             }
  93.         }
  94.         dp = move(dp2);
  95.     }
  96.  
  97.     int last_L = row_lengths.back();
  98.     long long total = 0;
  99.     for (int m : INDEP[last_L]) {
  100.         total = (total + dp[m]) % MOD;
  101.     }
  102.     return total;
  103. }
  104.  
  105. // LÕI XANH DƯƠNG: Tính số cách xếp gạch cho Lục giác đều
  106. long long H(int n) {
  107.     if (memoH[n] != -1) return memoH[n];
  108.  
  109.     vector<int> lengths;
  110.     for (int i = n; i < 2 * n; ++i) lengths.push_back(i);
  111.     for (int i = 2 * n - 2; i >= n; --i) lengths.push_back(i);
  112.  
  113.     return memoH[n] = count_independent_sets(lengths);
  114. }
  115.  
  116. // VÙNG GÓC XANH LÁ: Tính số cách xếp gạch cho góc (Hình thang)
  117. long long F(int n, int h) {
  118.     if (memoF[n][h] != -1) return memoF[n][h];
  119.  
  120.     int rows = h - 1;
  121.     vector<int> lengths;
  122.     for (int i = 0; i < rows; ++i) {
  123.         int l = (n - 2) - i;
  124.         lengths.push_back(max(0, l));
  125.     }
  126.  
  127.     return memoF[n][h] = count_independent_sets(lengths);
  128. }
  129.  
  130. // ĐỆ QUY CHÍNH: Bóc vỏ dải hình vuông màu cam
  131. long long R(int u, int v) {
  132.     if (memoR[u][v] != -1) return memoR[u][v];
  133.     if (v == 0) return memoR[u][v] = H(u); // Trúng lõi lục giác
  134.  
  135.     long long res = (u == 1 && v == 1) ? 1 : 0;
  136.     for (int w = 0; w < u; ++w) {
  137.         long long corner = F(u, u - w);
  138.         long long corner6 = power(corner, 6);
  139.         res = (res + R(v, w) * corner6) % MOD;
  140.     }
  141.  
  142.     return memoR[u][v] = res;
  143. }
  144.  
  145. // Điểm bắt đầu thuật toán
  146. long long T(int n) {
  147.     long long ans = (2 * R(n, n) - (n == 1 ? 1 : 0)) % MOD;
  148.     if (ans < 0) ans += MOD; // Xử lý modulo số âm trong C++
  149.     return ans;
  150. }
  151.  
  152. int main() {
  153.     // Tối ưu hóa I/O tốc độ cao
  154.     ios_base::sync_with_stdio(false);
  155.     cin.tie(NULL);
  156.  
  157.     int n;
  158.     if (cin >> n) {
  159.         if (n > 12) {
  160.             cout << "Canh bao: n = " << n << " co the vuot qua bo nho hoac chay lau (Time Limit Exceeded)!" << "\n";
  161.         }
  162.  
  163.         // Khởi tạo tất cả mảng ghi nhớ (Memoization) bằng -1
  164.         memset(memoH, -1, sizeof(memoH));
  165.         memset(memoF, -1, sizeof(memoF));
  166.         memset(memoR, -1, sizeof(memoR));
  167.  
  168.         // Chuẩn bị các mặt nạ bit (chỉ sinh tới mức n cần thiết để tiết kiệm RAM)
  169.         precompute_indep(n);
  170.  
  171.         // Tính và in kết quả
  172.         cout << T(n) << "\n";
  173.     }
  174.  
  175.     return 0;
  176. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/weHC7l
language:
C++14 (gcc 8.3)
created:
1 day 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!