[text] j

Viewer

  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <random>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  11. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  12. #define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  13. #define X first
  14. #define Y second
  15.  
  16. const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1};
  17. const int dy[8]={1, -1, 0, 0, 1, -1, 1, -1};
  18. const double EPS = 1e-8;
  19. const int mod = 1e9+7; // 1e9+7, 998244353
  20. const int phi = 1e9+6; // 1e9+7, 998244353
  21. // BEFORE coding are you sure you understood the statement correctly?
  22. // PLEASE do not forget to read the sample explanation carefully.
  23. // WATCH out for overflows & RTs in general.
  24. // TEST your idea or code on the corner cases.
  25. // ANALYZE each idea you have thoroughly.
  26.  
  27. const int M = 1e5+10;
  28. vector <int> pos[M];
  29.  
  30. void burn(int tc) {
  31.     int n, m, k; cin >> n >> m >> k;
  32.     vector <int> a(n);
  33.     for (int i = 0; i < n; i++) {
  34.         cin >> a[i], a[i]%=m;
  35.         pos[a[i]].push_back(i);
  36.     }
  37.     vector <int> nxt(n, -1);
  38.     set <int> done;
  39.     for (int i = 0; i < n; i++) {
  40.         if (done.count(a[i])) continue;
  41.         done.insert(a[i]);
  42.         for (int j = 1; j < pos[a[i]].size(); j++) {
  43.             nxt[pos[a[i]][j-1]] = pos[a[i]][j];
  44.         }
  45.     }
  46.     vector <vector <int>> dp(n, vector <int> (k+1, 0));
  47.     int sm = 0;
  48.     for (int i = 0; i < n; i++) {
  49.         dp[i][1] += 1+sm;
  50.         if (dp[i][1] >= mod) dp[i][1]-=mod;
  51.         for (int j = 1; j < k; j++) {
  52.             if (~nxt[i]) {
  53.                 dp[nxt[i]][j+1]+=dp[i][j];
  54.                 dp[nxt[i]][j]+=dp[i][j];
  55.                 if (dp[nxt[i]][j+1] >= mod) dp[nxt[i]][j+1]-=mod;
  56.                 if (dp[nxt[i]][j] >= mod) dp[nxt[i]][j]-=mod;
  57.             }
  58.         }
  59.         sm+=dp[i][k];
  60.         if (sm >= mod) sm-=mod;
  61.     }
  62.     cout << sm;
  63.     for (int i = 0; i < n; i++) {
  64.         pos[a[i]].pop_back();
  65.     }
  66. }
  67.  
  68. int main()
  69. {
  70.     AboTaha_on_da_code
  71.  
  72.     freopen("fortune.in", "r", stdin);
  73. //    freopen("output.txt", "w", stdout);
  74.  
  75.     int T = 1; cin >> T;
  76.  
  77.     for (int i = 1; i <= T; i++) {
  78. //        cout << "Case " << i << ": ";
  79.         burn(i);
  80.         cout << '\n';
  81.     }
  82.     return (0-0);
  83. }

Editor

You can edit this paste and save as new:


File Description
  • j
  • Paste Code
  • 06 Jul-2024
  • 2.38 Kb
You can Share it: