fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MOD 1000000009
  4.  
  5. vector<long long> fact, inv_fact;
  6.  
  7. // Fast modular exponentiation
  8. long long power(long long base, long long exp, long long mod) {
  9.     long long result = 1;
  10.     base %= mod;
  11.     while (exp > 0) {
  12.         if (exp & 1) result = (result * base) % mod;
  13.         base = (base * base) % mod;
  14.         exp >>= 1;
  15.     }
  16.     return result;
  17. }
  18.  
  19. // Precompute factorials and their modular inverses
  20. void precomputeFactorials(int max_n) {
  21.     fact.resize(max_n + 1);
  22.     inv_fact.resize(max_n + 1);
  23.  
  24.     // Compute factorials
  25.     fact[0] = 1;
  26.     for (int i = 1; i <= max_n; i++) {
  27.         fact[i] = (fact[i-1] * i) % MOD;
  28.     }
  29.  
  30.     // Compute modular inverses using Fermat's little theorem
  31.     // inv_fact[i] = (i!)^(-1) mod MOD = (i!)^(MOD-2) mod MOD
  32.     inv_fact[max_n] = power(fact[max_n], MOD - 2, MOD);
  33.     for (int i = max_n - 1; i >= 0; i--) {
  34.         inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
  35.     }
  36. }
  37.  
  38. // Calculate multinomial coefficient: n! / (c1! * c2! * ... * cm!)
  39. long long multinomial(int n, const vector<int>& counts) {
  40.     long long result = fact[n];
  41.     for (int c : counts) {
  42.         result = (result * inv_fact[c]) % MOD;
  43.     }
  44.     return result;
  45. }
  46.  
  47. long long solve(int n, int m, vector<int>& arr) {
  48.         // Edge cases
  49.         if (n == 0) return 1;
  50.         if (m <= 1) return 1;
  51.  
  52.         // Remove colors with 0 balls and filter valid counts
  53.         vector<int> counts;
  54.         for (int x : arr) {
  55.             if (x > 0) {
  56.                 counts.push_back(x);
  57.             }
  58.         }
  59.  
  60.         // If we have <= 1 colors with balls, only 1 arrangement possible
  61.         if (counts.size() <= 1) return 1;
  62.  
  63.         // Precompute factorials up to n
  64.         precomputeFactorials(n);
  65.  
  66.         // Sort counts in descending order to find two largest easily
  67.         sort(counts.begin(), counts.end(), greater<int>());
  68.  
  69.         vector<int> newCounts;
  70.         newCounts.push_back(counts[0] + counts[1]); // Merge two largest
  71.  
  72.         for (int i = 2; i < counts.size(); i++) {
  73.             newCounts.push_back(counts[i]);
  74.         }
  75.  
  76.         return multinomial(n, newCounts);
  77. }
  78.  
  79. int main() {
  80. 	int n, m;
  81.     cin >> n >> m;
  82.     vector<int> arr(m);
  83.     for (int i = 0; i < m; i++) {
  84.         cin >> arr[i];
  85.     }
  86.     cout << solve(n, m, arr) << "\n";
  87. 	return 0;
  88. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
3 2
1 2
stdout 
1
https://ideone.com/7CMfDr
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!