fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const int MOD = 998244353;
  6.  
  7. // Fast modular exponentiation.
  8. ll modexp(ll base, ll exp, ll mod) {
  9.     ll result = 1;
  10.     base %= mod;
  11.     while(exp > 0){
  12.         if(exp & 1)
  13.             result = (result * base) % mod;
  14.         base = (base * base) % mod;
  15.         exp >>= 1;
  16.     }
  17.     return result;
  18. }
  19.  
  20. int main(){
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr);
  23.  
  24.     int t;
  25.     cin >> t;
  26.  
  27.     // Precompute factorials and inverse factorials up to the maximum sum possible.
  28.     // The maximum total sum over any test case is at most 5e5.
  29.     int maxN = 500000;
  30.     vector<ll> fact(maxN+1), invfact(maxN+1);
  31.     fact[0] = 1;
  32.     for (int i = 1; i <= maxN; i++){
  33.         fact[i] = fact[i-1] * i % MOD;
  34.     }
  35.     invfact[maxN] = modexp(fact[maxN], MOD-2, MOD);
  36.     for (int i = maxN; i >= 1; i--){
  37.         invfact[i-1] = invfact[i] * i % MOD;
  38.     }
  39.  
  40.     while(t--){
  41.         vector<int> c(26);
  42.         int total = 0;
  43.         for (int i = 0; i < 26; i++){
  44.             cin >> c[i];
  45.             total += c[i];
  46.         }
  47.         int oddCount = (total + 1) / 2; // number of odd positions (1-indexed)
  48.         int evenCount = total / 2;      // number of even positions
  49.  
  50.         // DP to count valid partitions: dp[j] = number of ways to choose a subset (from letters with c > 0)
  51.         // such that the sum of chosen counts equals j.
  52.         vector<ll> dp(total+1, 0), newdp(total+1, 0);
  53.         dp[0] = 1;
  54.         for (int i = 0; i < 26; i++){
  55.             if(c[i] == 0) continue; // skip letters with zero occurrences
  56.             int x = c[i];
  57.             fill(newdp.begin(), newdp.end(), 0);
  58.             for (int j = 0; j <= total; j++){
  59.                 if(dp[j] != 0){
  60.                     // Option 1: assign letter i to even positions (sum remains j)
  61.                     newdp[j] = (newdp[j] + dp[j]) % MOD;
  62.                     // Option 2: assign letter i to odd positions (sum increases by x)
  63.                     if(j + x <= total)
  64.                         newdp[j + x] = (newdp[j + x] + dp[j]) % MOD;
  65.                 }
  66.             }
  67.             dp.swap(newdp);
  68.         }
  69.  
  70.         ll waysToAssign = dp[oddCount] % MOD;
  71.  
  72.         // The number of arrangements once the assignment is fixed is:
  73.         // (oddCount)! * (evenCount)! divided by the product of factorials of counts of each letter.
  74.         ll arrangement = (fact[oddCount] * fact[evenCount]) % MOD;
  75.         for (int i = 0; i < 26; i++){
  76.             arrangement = (arrangement * invfact[c[i]]) % MOD;
  77.         }
  78.  
  79.         ll ans = (waysToAssign * arrangement) % MOD;
  80.         cout << ans % MOD << "\n";
  81.     }
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.03s 18356KB
comments (?)
stdin
copy 
5
2 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 233527 233827
stdout
copy 
4
960
0
1
789493841
https://ideone.com/RhL6xz
language:
C++ (gcc 8.3)
created:
1 day 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!