fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // Dùng kiểu long long cho N và P để đảm bảo đủ lớn
  8. typedef long long ll;
  9.  
  10. void solve() {
  11.     ll N;
  12.     int M, K;
  13.     ll P;
  14.  
  15.     // Đọc input: N, M, K, P
  16.     if (!(cin >> N >> M >> K >> P)) {
  17.         return;
  18.     }
  19.  
  20.     // Pmax là tổng chênh lệch tối đa: (K-1) * M
  21.     int P_max = (K - 1) * M;
  22.  
  23.     // DP: f[k][s] là số chuỗi k ngày có tổng chênh lệch s.
  24.     // Dùng vector 2D để lưu DP (k chỉ chạy đến K, s chỉ chạy đến P_max)
  25.     // Kích thước: (K+1) x (P_max + 1)
  26.     vector<vector<ll>> f(K + 1, vector<ll>(P_max + 1, 0));
  27.  
  28.     // G[k][s] là tổng tiền tố: sum_{j=0}^{s} f[k][j]
  29.     vector<vector<ll>> G(K + 1, vector<ll>(P_max + 1, 0));
  30.  
  31.     // --- 1. Trường hợp cơ sở: k=1 ---
  32.     // f[1][0] = 1 (chênh lệch 0)
  33.     f[1][0] = 1;
  34.     // G[1][s] = 1 cho s >= 0
  35.     for (int s = 0; s <= P_max; ++s) {
  36.         G[1][s] = 1;
  37.     }
  38.  
  39.     // --- 2. Tính DP từ k=2 đến K ---
  40.     for (int k = 2; k <= K; ++k) {
  41.         // Tổng chênh lệch min: k-1
  42.         int s_min = k - 1; 
  43.         // Tổng chênh lệch max: (k-1) * M
  44.  
  45.         for (int s = s_min; s <= P_max; ++s) {
  46.             // Công thức truy hồi tối ưu: f[k][s] = G[k-1][s-1] - G[k-1][s-M-1]
  47.             // G[k-1][s-1]: tổng đến s-1
  48.             ll sum_upper = G[k - 1][s - 1]; 
  49.  
  50.             // G[k-1][s-M-1]: tổng đến s-M-1
  51.             ll sum_lower = 0;
  52.             if (s - M - 1 >= 0) {
  53.                 sum_lower = G[k - 1][s - M - 1];
  54.             }
  55.  
  56.             // f[k][s] = (sum_upper - sum_lower) mod P
  57.             ll current_f = (sum_upper - sum_lower + P) % P; 
  58.             f[k][s] = current_f;
  59.  
  60.             // Cập nhật tổng tiền tố G[k][s]
  61.             G[k][s] = (G[k][s - 1] + f[k][s]) % P;
  62.         }
  63.     }
  64.  
  65.     // --- 3. Tính kết quả cuối cùng ---
  66.     ll S0 = 0; // S0 = sum f[K][s]
  67.     ll S1 = 0; // S1 = sum s * f[K][s]
  68.  
  69.     // Bắt đầu từ chênh lệch tối thiểu: K-1
  70.     int s_start = K - 1; 
  71.  
  72.     for (int s = s_start; s <= P_max; ++s) {
  73.         if (f[K][s] == 0) continue; // Bỏ qua nếu f[K][s] = 0
  74.  
  75.         // Tính S0
  76.         S0 = (S0 + f[K][s]) % P;
  77.  
  78.         // Tính S1 = sum s * f[K][s]
  79.         // (s * f[K][s]) mod P
  80.         ll term_s1 = ((ll)s % P) * (f[K][s] % P) % P;
  81.         S1 = (S1 + term_s1) % P;
  82.     }
  83.  
  84.     // Công thức: Answer = (N * S0 - S1) mod P
  85.     // N mod P:
  86.     ll N_mod_P = N % P;
  87.  
  88.     // (N_mod_P * S0) mod P
  89.     ll term_N_S0 = (N_mod_P * S0) % P;
  90.  
  91.     // Answer = (term_N_S0 - S1 + P) mod P (Đảm bảo kết quả dương)
  92.     ll final_answer = (term_N_S0 - S1 + P) % P;
  93.  
  94.     cout << final_answer << endl;
  95. }
  96.  
  97. int main() {
  98.     // Tăng tốc độ I/O
  99.     ios_base::sync_with_stdio(false);
  100.     cin.tie(NULL);
  101.  
  102.     solve();
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
3001 400 6 9901
stdout
copy 
4227
https://ideone.com/vcHAnP
language:
C++14 (gcc 8.3)
created:
9 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!