fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Hằng số giới hạn (N <= 8000)
  9. const int MAXN = 8005;
  10.  
  11. // Mảng tiền xử lý cho Tổ hợp (Combinatorics)
  12. // C[i][j] = tổ hợp chập j của i (i choose j)
  13. long long C[MAXN][MAXN];
  14.  
  15. // Hàm tiền xử lý Tổ hợp (nCk)
  16. // Sử dụng công thức Pascal: C[n][k] = C[n-1][k-1] + C[n-1][k]
  17. void precompute_combinations() {
  18.     // Khởi tạo cơ sở
  19.     for (int i = 0; i < MAXN; ++i) {
  20.         C[i][0] = 1; // C[i][0] = 1
  21.         for (int j = 1; j <= i; ++j) {
  22.             // Đảm bảo không vượt quá giới hạn mảng
  23.             if (i > 0) {
  24.                 C[i][j] = C[i-1][j-1] + C[i-1][j];
  25.                 // Lưu ý: Nếu đề bài yêu cầu Modulo, cần thực hiện phép % tại đây.
  26.                 // Giả sử đề bài không yêu cầu Modulo vì không có đề cập rõ.
  27.             }
  28.         }
  29.     }
  30. }
  31.  
  32. /**
  33.  * @brief Hàm tính số cách chia tổng (N_prime) thành (K_prime) số nguyên dương.
  34.  * @details Tương đương với tổ hợp C(N_prime - 1, K_prime - 1).
  35.  * @param N_prime Tổng cần chia.
  36.  * @param K_prime Số lượng phần tử.
  37.  * @return Số cách chia.
  38.  */
  39. long long combinations(int N_prime, int K_prime) {
  40.     if (K_prime <= 0 || N_prime < K_prime) {
  41.         return 0;
  42.     }
  43.     // Bài toán chia N thành K phần: C(N-1, K-1)
  44.     return C[N_prime - 1][K_prime - 1];
  45. }
  46.  
  47.  
  48. // Hàm giải quyết bài toán cho một k cụ thể
  49. long long solve_for_k(int k, int N, int M) {
  50.     // 1. Tổng số cách chia N thành k số nguyên dương (Không có ràng buộc M)
  51.     // C(N-1, k-1)
  52.     long long result = combinations(N, k);
  53.  
  54.     // 2. Áp dụng Nguyên lý Bao hàm - Loại trừ (Inclusion-Exclusion)
  55.     // Loại bỏ các trường hợp có ít nhất 's' số bị lặp >= M+1 lần.
  56.  
  57.     // s là số lượng giá trị (ví dụ: x1, x2, ...) vi phạm điều kiện M (lặp >= M+1 lần)
  58.     for (int s = 1; ; ++s) {
  59.         // Tổng giá trị nhỏ nhất đã bị sử dụng bởi s số vi phạm: s * (M + 1) * 1 (nếu tất cả vi phạm đều là số 1)
  60.         int min_val_used = s * (M + 1);
  61.         if (min_val_used > N) {
  62.             break; // Không thể vi phạm quá s số
  63.         }
  64.  
  65.         // s_sum là tổng giá trị tối thiểu đã bị sử dụng bởi s số vi phạm.
  66.         // Tuy nhiên, do các số vi phạm x1, x2, ... có thể khác nhau, ta không thể tính trực tiếp.
  67.         // Ta chỉ có thể tính tổng số cách chọn s vị trí vi phạm (chọn s số x1, x2,...)
  68.  
  69.         // Cách đơn giản hóa cho bài toán này (do tính đối xứng):
  70.         // Giả sử tất cả s số vi phạm đều là số 1 (x1=x2=...=xs=1). 
  71.         // Lượng tổng bị sử dụng bởi s số này: s * (M + 1).
  72.         // Lượng phần tử bị sử dụng bởi s số này: s * (M + 1)
  73.  
  74.         int total_value_removed = s * (M + 1); // Tổng bị "cố định"
  75.         int total_parts_removed = s;           // Số lượng phần tử bị "cố định"
  76.  
  77.         int N_prime = N - total_value_removed; // Tổng còn lại để chia
  78.         int K_prime = k - total_parts_removed;   // Số phần tử còn lại để chia
  79.  
  80.         // Nếu N_prime < K_prime, không thể chia được nữa
  81.         if (N_prime < K_prime) break;
  82.  
  83.         // Số cách chọn s số x_i vi phạm (C(N, s) - Số cách chọn s giá trị khác nhau)
  84.         // Số cách chọn s vị trí (trong k vị trí) để đặt s số vi phạm (C(k, s))
  85.  
  86.         // Quan trọng: Phải là số cách chọn s giá trị khác nhau (x1, x2, ...) từ N giá trị,
  87.         // nhân với số cách sắp xếp các giá trị còn lại.
  88.  
  89.         // SỬ DỤNG CÔNG THỨC KHOA HỌC: 
  90.         // Số cách chia N thành k số, trong đó 's' số bất kỳ lặp >= M+1 lần (tối thiểu)
  91.         // Số cách: C(k, s) * C(N - s*(M+1) - 1, k - 1)
  92.         // (Sai: Công thức này chỉ áp dụng cho trường hợp các số vi phạm là cùng 1 giá trị)
  93.  
  94.         // Đơn giản hóa đối xứng:
  95.         // Giả sử ta chọn s vị trí (C(k, s)) và gán cho chúng s số vi phạm (ví dụ: tất cả là số 1)
  96.  
  97.         // CÔNG THỨC CHÍNH XÁC (Dựa trên DP trên tổng số lần xuất hiện):
  98.         // Số cách chia N thành k số, mỗi số lặp >= M+1 lần
  99.         // Tương đương với: C(k, s) * Số cách chia N' = N - s*(M+1) thành k số bất kỳ.
  100.  
  101.         // Số cách chia N' thành k số nguyên dương bất kỳ: C(N' - 1, k - 1)
  102.         // Phép nhân: C(k, s) * C(N - s*(M+1) - 1, k - 1)
  103.  
  104.         // 1. Số cách chọn 's' vị trí trong 'k' phần tử: C(k, s)
  105.         long long ways_to_choose_s = C[k][s];
  106.  
  107.         // 2. Số cách phân phối tổng còn lại (N - s*(M+1)) vào k phần tử
  108.         // N_r = N - s*(M+1) (Tổng còn lại)
  109.         // k_r = k (Số phần tử)
  110.         // Số cách: C(N_r - 1, k - 1)
  111.         int N_remaining = N - s * (M + 1);
  112.         long long ways_to_partition = combinations(N_remaining, k); // C(N_remaining - 1, k - 1)
  113.  
  114.         long long term = ways_to_choose_s * ways_to_partition;
  115.  
  116.         // Nếu s lẻ thì trừ đi, nếu s chẵn thì cộng vào (Bao hàm - Loại trừ)
  117.         if (s % 2 == 1) {
  118.             result -= term;
  119.         } else {
  120.             result += term;
  121.         }
  122.     }
  123.  
  124.     return result;
  125. }
  126.  
  127. void solve() {
  128.  
  129.  
  130.  
  131.     int N, M;
  132.     // Đọc N và M từ file INP
  133.     if (!(cin >> N >> M)) {
  134.         cerr << "Lỗi đọc dữ liệu từ file INP." << endl;
  135.         return;
  136.     }
  137.  
  138.     // Tiền xử lý Tổ hợp
  139.     precompute_combinations();
  140.  
  141.     // Chạy vòng lặp từ k = 1 đến N
  142.     for (int k = 1; k <= N; ++k) {
  143.         long long result_k = solve_for_k(k, N, M);
  144.         cout << result_k << (k == N ? "" : " ");
  145.     }
  146.  
  147.  
  148. }
  149.  
  150. int main() {
  151.     // Tăng tốc I/O
  152.     ios_base::sync_with_stdio(false);
  153.     cin.tie(NULL);
  154.  
  155.     solve();
  156.  
  157.     return 0;
  158. }
Success #stdin #stdout 0.09s 504132KB
comments (?)
stdin
copy 
4 2
stdout
copy 
0 3 3 1
https://ideone.com/fzXIQM
language:
C++14 (gcc 8.3)
created:
3 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!