fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const long long MOD = 1e9 + 7;
  9.  
  10. long long cnt = 0;
  11. vector<long long> A;
  12. unordered_map<long long, long long> memo[305]; // Giới hạn mảng theo số lượng phần tử tối đa
  13.  
  14. // Hàm tính lũy thừa nhị phân cho 2^cnt
  15. long long power(long long base, long long exp) {
  16.     long long res = 1;
  17.     base %= MOD;
  18.     while (exp > 0) {
  19.         if (exp % 2 == 1) res = (res * base) % MOD;
  20.         base = (base * base) % MOD;
  21.         exp /= 2;
  22.     }
  23.     return res;
  24. }
  25.  
  26. // Quy hoạch động đệ quy có nhớ theo chuẩn logic chỉ định
  27. long long dp(int i, long long j) {
  28.     if (i == 0) {
  29.         if (j == 0) return 0;
  30.         else return 1;
  31.     }
  32.  
  33.     if (j == 0) return 0;
  34.     if (j == 1) return 1;
  35.  
  36.     // Trả về nếu đã lưu trong map
  37.     if (memo[i].count(j)) return memo[i][j];
  38.  
  39.     // Gọi đệ quy: Không chọn A[i-1] + Chọn A[i-1]
  40.     long long res = dp(i - 1, j);
  41.     res = (res + dp(i - 1, j / A[i - 1])) % MOD; // A[i-1] do vector đánh index từ 0
  42.  
  43.     return memo[i][j] = res;
  44. }
  45.  
  46. int main() {
  47.     // Tối ưu I/O
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.  
  51.     int Q;
  52.     long long L, R;
  53.     if (!(cin >> Q >> L >> R)) return 0;
  54.  
  55.     while (Q--) {
  56.         char type;
  57.         long long x;
  58.         cin >> type >> x;
  59.  
  60.         // Xử lý thao tác Thêm / Xóa
  61.         if (type == '+') {
  62.             if (x == 1) {
  63.                 cnt++;
  64.             } else {
  65.                 A.push_back(x);
  66.                 sort(A.begin(), A.end()); // Đảm bảo dãy tăng dần
  67.             }
  68.         } else if (type == '-') {
  69.             if (x == 1) {
  70.                 cnt--;
  71.             } else {
  72.                 auto it = find(A.begin(), A.end(), x);
  73.                 if (it != A.end()) {
  74.                     A.erase(it);
  75.                 }
  76.             }
  77.         }
  78.  
  79.         int n = A.size();
  80.  
  81.         // Clear mảng nhớ trạng thái trước khi đệ quy lại từ đầu
  82.         for (int i = 0; i <= n; i++) {
  83.             memo[i].clear();
  84.         }
  85.  
  86.         // Tính kết quả cho đoạn [L, R]
  87.         long long ansR = dp(n, R);
  88.         long long ansL = (L > 1) ? dp(n, L - 1) : 0;
  89.  
  90.         // Áp dụng công thức số cách = (dp(R) - dp(L-1)) * 2^cnt
  91.         long long final_ans = (ansR - ansL + MOD) % MOD;
  92.         final_ans = (final_ans * power(2, cnt)) % MOD;
  93.  
  94.         cout << final_ans << "\n";
  95.     }
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
15 1 1000000000
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1000000000
+ 1
+ 1
+ 1
+ 2
- 1
- 1
+ 1
+ 1
+ 1
stdout
copy 
2
4
8
16
32
64
128
256
512
768
384
192
384
768
1536
https://ideone.com/1iNbDY
language:
C++14 (gcc 8.3)
created:
4 hours 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!