API tools faq
paste
Advertisement
gitman3

Arraangia

gitman3
Jul 13th, 2025 (edited)
65
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long MOD = 998244353;
  6.  
  7. long long power(long long base, long long exp) {
  8.     long long res = 1;
  9.     base %= MOD;
  10.     while (exp > 0) {
  11.         if (exp % 2 == 1) res = (res * base) % MOD;
  12.         base = (base * base) % MOD;
  13.         exp /= 2;
  14.     }
  15.     return res;
  16. }
  17.  
  18. long long modInverse(long long n) {
  19.     return power(n, MOD - 2);
  20. }
  21.  
  22. vector<long long> fact;
  23. vector<long long> invFact;
  24.  
  25. void precompute_factorials(int n) {
  26.     fact.resize(n + 1);
  27.     invFact.resize(n + 1);
  28.     fact[0] = 1;
  29.     invFact[0] = 1;
  30.     for (int i = 1; i <= n; i++) {
  31.         fact[i] = (fact[i - 1] * i) % MOD;
  32.         invFact[i] = modInverse(fact[i]);
  33.     }
  34. }
  35.  
  36. long long nCr_mod_p(int n, int r) {
  37.     if (r < 0 || r > n) {
  38.         return 0;
  39.     }
  40.     return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
  41. }
  42.  
  43. long long clac(int N, int K, vector<int>& A) {
  44.     sort(A.begin(), A.end());
  45.    
  46.     map<int, int> counts;
  47.     for (int x : A) {
  48.         counts[x]++;
  49.     }
  50.    
  51.     vector<int> c_values;
  52.     for(auto const& [val, num] : counts){
  53.         c_values.push_back(num);
  54.     }
  55.  
  56.     precompute_factorials(N + 5);
  57.    
  58.     vector<long long> dp(N + 1, 0);
  59.     dp[0] = 1;
  60.     int current_size = c_values[0];
  61.  
  62.     for (size_t i = 1; i < c_values.size(); ++i) {
  63.         vector<long long> next_dp(N + 1, 0);
  64.         int c = c_values[i];
  65.         int n_prev = current_size;
  66.        
  67.         for (int j = 0; j <= n_prev + c && j <= K; ++j) {
  68.             long long total_ways = 0;
  69.             for (int k = 0; k <= j && k < n_prev; ++k) {
  70.                 if (dp[k] == 0) continue;
  71.                
  72.                 int l = j - k;
  73.                 if (l < 0 || l > c) continue;
  74.                
  75.                 long long term1 = nCr_mod_p(n_prev - k, l);
  76.                 long long term2 = nCr_mod_p(c + k, j);
  77.                
  78.                 long long ways = (term1 * term2) % MOD;
  79.                 total_ways = (total_ways + (dp[k] * ways) % MOD) % MOD;
  80.             }
  81.             next_dp[j] = total_ways;
  82.         }
  83.        
  84.         dp = next_dp;
  85.         current_size += c;
  86.     }
  87.  
  88.     if (K >= current_size) return 0;
  89.     return dp[K];
  90. }
  91.  
  92. int main() {
  93.     int N, K;
  94.     cin >> N >> K;
  95.  
  96.     vector<int> A(N);
  97.     for (int i = 0; i < N; ++i) {
  98.         cin >> A[i];
  99.     }
  100.  
  101.     long long result = clac(N, K, A);
  102.     cout << result << endl;
  103.  
  104.     return 0;
  105. }
  106.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!