fork download
copy 
  1. #include <bits/stdc++.h> // Thư viện tổng hợp, chứa vector, iostream, etc.
  2. using namespace std;
  3.  
  4. // Hằng số modulo. Kết quả cuối cùng phải chia lấy dư cho số này.
  5. const int MOD = 1e9 + 7;
  6.  
  7. // ======================================================================
  8. // "CỖ MÁY" FWHT - Trái tim của thuật toán
  9. // Hàm này thực hiện cả biến đổi xuôi và ngược.
  10. // a: Mảng cần biến đổi (sẽ bị thay đổi trực tiếp).
  11. // inverse: cờ điều khiển.
  12. //   - false: Biến đổi xuôi (FWHT xuôi), dùng phép cộng.
  13. //   - true: Biến đổi ngược (FWHT ngược), dùng phép trừ.
  14. // ======================================================================
  15. void fwht_or(vector<long long>& a, bool inverse) {
  16.     int n = a.size(); // Kích thước mảng, luôn là lũy thừa của 2.
  17.  
  18.     // len: Kích thước của "một nửa nhóm" đang xét. Bắt đầu từ 1, 2, 4, ...
  19.     for (int len = 1; len < n; len <<= 1) { // len <<= 1 tương đương len = len * 2
  20.  
  21.         // i: Điểm bắt đầu của các "nhóm lớn" (kích thước 2*len).
  22.         // Nó nhảy qua từng nhóm lớn một.
  23.         for (int i = 0; i < n; i += 2 * len) {
  24.  
  25.             // j: Vị trí tương ứng trong mỗi nửa nhóm.
  26.             // Để ghép cặp phần tử thứ j của nửa đầu với phần tử thứ j của nửa sau.
  27.             for (int j = 0; j < len; j++) {
  28.  
  29.                 // u: Phần tử ở nửa đầu của nhóm.
  30.                 long long u = a[i + j];
  31.  
  32.                 // v: Phần tử tương ứng ở nửa sau của nhóm.
  33.                 long long v = a[i + len + j];
  34.  
  35.                 // Logic biến đổi cốt lõi
  36.                 if (!inverse) {
  37.                     // Biến đổi xuôi: a' = a + b
  38.                     // Nửa sau sẽ cộng dồn thông tin từ nửa đầu.
  39.                     a[i + len + j] = (v + u) % MOD;
  40.                 } else {
  41.                     // Biến đổi ngược: a = a' - b
  42.                     // Nửa sau sẽ loại bỏ thông tin đã được cộng vào ở bước xuôi.
  43.                     a[i + len + j] = (v - u + MOD) % MOD; // +MOD để đảm bảo kết quả không âm
  44.                 }
  45.             }
  46.         }
  47.     }
  48. }
  49.  
  50.  
  51. int main() {
  52.     // Tối ưu hóa tốc độ nhập xuất
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(nullptr);
  55.  
  56.     // ======================================================================
  57.     // BƯỚC 0: ĐỌC DỮ LIỆU VÀ CHUẨN BỊ
  58.     // ======================================================================
  59.     int n;
  60.     cin >> n; // Đọc kích thước mảng gốc
  61.  
  62.     // FWHT yêu cầu kích thước mảng phải là lũy thừa của 2.
  63.     // Tìm N là lũy thừa của 2 nhỏ nhất >= n.
  64.     int N = 1;
  65.     while (N < n) {
  66.         N *= 2;
  67.     }
  68.  
  69.     // Tạo vector `a` với kích thước N. Các phần tử thừa (từ n đến N-1)
  70.     // sẽ có giá trị 0, không ảnh hưởng đến tổng.
  71.     vector<long long> a(N, 0);
  72.     for (int i = 0; i < n; ++i) {
  73.         cin >> a[i];
  74.     }
  75.  
  76.     // TRẠNG THÁI HIỆN TẠI: `a` chứa các giá trị gốc {a₀, a₁, ..., aₙ₋₁, 0, 0, ...}
  77.  
  78.  
  79.     // ======================================================================
  80.     // BƯỚC 1 & 2: KẾ HOẠCH & FWHT XUÔI
  81.     // Kế hoạch: Tính mảng C. Để làm vậy, ta biến đổi `a` sang "thế giới song song".
  82.     // ======================================================================
  83.     fwht_or(a, false); // Gọi "cỗ máy" ở chế độ xuôi.
  84.  
  85.     // TRẠNG THÁI HIỆN TẠI: `a` đã bị biến đổi. Nó không còn chứa giá trị gốc.
  86.     // Giờ đây nó chứa mảng `hat_a`, với a[k] = tổng các a_gốc[i] mà i là submask của k.
  87.  
  88.  
  89.     // ======================================================================
  90.     // BƯỚC 3: PHÉP NHÂN "THẦN KỲ"
  91.     // Đây là "đường tắt" O(N) để thực hiện phép tích chập.
  92.     // ======================================================================
  93.     for (int i = 0; i < N; ++i) {
  94.         a[i] = (a[i] * a[i]) % MOD;
  95.     }
  96.  
  97.     // TRẠNG THÁI HIỆN TẠI: `a` bây giờ chứa mảng `hat_C`.
  98.     // hat_C[k] = hat_a[k] * hat_a[k].
  99.     // Đây là mảng C nhưng vẫn đang ở "thế giới song song".
  100.  
  101.  
  102.     // ======================================================================
  103.     // BƯỚC 4: FWHT NGƯỢC
  104.     // Đưa kết quả từ "thế giới song song" trở về "thế giới thực".
  105.     // ======================================================================
  106.     fwht_or(a, true); // Gọi "cỗ máy" ở chế độ ngược.
  107.  
  108.     // TRẠNG THÁI HIỆN TẠI: `a` bây giờ chứa mảng `C`.
  109.     // a[k] = C[k] = tổng của tất cả a_gốc[i] * a_gốc[j] mà i | j = k.
  110.     // Chúng ta đã thành công tính được mảng trung gian quan trọng nhất.
  111.  
  112.  
  113.     // ======================================================================
  114.     // BƯỚC 5: TÍNH TỔNG TIỀN TỐ ĐỂ RA KẾT QUẢ CUỐI CÙNG
  115.     // Từ mảng C, ta tính S(U) = C[0] + C[1] + ... + C[U].
  116.     // ======================================================================
  117.     vector<long long> result(n); // Vector để chứa n đáp án cuối cùng.
  118.  
  119.     // S(0) chính là C[0] (tức là a[0] hiện tại).
  120.     if (n > 0) {
  121.         result[0] = a[0];
  122.     }
  123.  
  124.     // Vòng lặp tính các S(U) còn lại.
  125.     // result[i] tương ứng với S(i).
  126.     // S(i) = S(i-1) + C[i]
  127.     for (int i = 1; i < n; ++i) {
  128.         result[i] = (result[i - 1] + a[i]) % MOD;
  129.     }
  130.  
  131.     // TRẠNG THÁI HIỆN TẠI: `result` chứa các đáp án S(0), S(1), ..., S(n-1).
  132.  
  133.  
  134.     // ======================================================================
  135.     // IN KẾT QUẢ
  136.     // ======================================================================
  137.     for (int i = 0; i < n; ++i) {
  138.         cout << result[i] << (i == n - 1 ? "" : " ");
  139.     }
  140.     cout << endl;
  141.  
  142.     return 0;
  143. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/7D1MH5
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
8 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!