Advertisement
Guest User

Untitled

a guest
Dec 8th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define p pair <int, int>
  4. #define s second
  5. #define f first
  6. #define ll long long
  7.  
  8. using namespace std;
  9.  
  10. int main() {
  11.     ios_base::sync_with_stdio(0);
  12.     cin.tie(0); cout.tie(0);
  13.     int n, m, k;
  14.     cin >> k >> n >> m;
  15.     vector <vector <int>> dp(n + 1, vector <int> (k + 1));
  16.     vector <int> sum(k + 1);
  17.     for (int i = 0; i < n; i++) dp[i][1] = i;
  18.     for (int i = 1; i <= n; i++) {
  19.         for (int j = 1; j <= k; j++) {
  20.             dp[i][j] = (dp[i - 1][j] + sum[j - 1]) % m;
  21.             if (i % 4 == 0) dp[i][j] = (dp[i][j] - dp[i - 4][j - 1] + m) % m;
  22.             if (i % 2 == 0) dp[i][j] = (dp[i][j] - dp[i - 2][j - 1] + m) % m;
  23.             sum[j] += dp[i][j];
  24.         }
  25.     }
  26.     cout << dp[n][k];
  27.     return 0;
  28. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement