fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll MOD = 998244353;
  6.  
  7. // Maximum total count among test cases is <= 5e5.
  8. const int MAXN = 500000;
  9.  
  10. vector<ll> fact(MAXN+1), invfact(MAXN+1);
  11.  
  12. // Fast exponentiation modulo mod.
  13. ll modexp(ll base, ll exp, ll mod=MOD) {
  14.     ll res = 1;
  15.     base %= mod;
  16.     while(exp > 0) {
  17.         if(exp & 1)
  18.             res = (res * base) % mod;
  19.         base = (base * base) % mod;
  20.         exp >>= 1;
  21.     }
  22.     return res;
  23. }
  24.  
  25. // Precompute factorials and inverse factorials up to MAXN.
  26. void precomputeFactorials() {
  27.     fact[0] = 1;
  28.     for (int i = 1; i <= MAXN; i++) {
  29.         fact[i] = (fact[i-1] * i) % MOD;
  30.     }
  31.     invfact[MAXN] = modexp(fact[MAXN], MOD - 2, MOD);
  32.     for (int i = MAXN; i > 0; i--) {
  33.         invfact[i-1] = (invfact[i] * i) % MOD;
  34.     }
  35. }
  36.  
  37. int main(){
  38.     ios::sync_with_stdio(false);
  39.     cin.tie(nullptr);
  40.  
  41.     precomputeFactorials();
  42.  
  43.     int t; 
  44.     cin >> t;
  45.     while(t--){
  46.         vector<int> c(26);
  47.         ll total = 0;
  48.         for (int i = 0; i < 26; i++){
  49.             cin >> c[i];
  50.             total += c[i];
  51.         }
  52.         // Total length of string must be positive.
  53.         if(total == 0){
  54.             cout << 0 << "\n";
  55.             continue;
  56.         }
  57.  
  58.         int oddCount = (total + 1) / 2; // positions: 1,3,5,...
  59.         int evenCount = total / 2;      // positions: 2,4,6,...
  60.  
  61.         // DP for subset-sum: For each letter (with c[i]>0), decide if it goes to odd positions.
  62.         // We need the sum of counts chosen to equal oddCount.
  63.         vector<ll> dp(oddCount+1, 0);
  64.         dp[0] = 1;
  65.         for (int i = 0; i < 26; i++){
  66.             if(c[i] <= 0) continue; // ignore letters that do not appear.
  67.             int cnt = c[i];
  68.             for (int j = oddCount; j >= cnt; j--){
  69.                 dp[j] = (dp[j] + dp[j - cnt]) % MOD;
  70.             }
  71.         }
  72.  
  73.         ll waysPartition = dp[oddCount] % MOD;
  74.  
  75.         // If no valid partition exists, answer is 0.
  76.         if(waysPartition == 0){
  77.             cout << 0 << "\n";
  78.             continue;
  79.         }
  80.  
  81.         // The arrangement factor is:
  82.         // (fact[oddCount] * fact[evenCount]) / (∏_{i=0}^{25} c[i]!)
  83.         ll arrangement = (fact[oddCount] * fact[evenCount]) % MOD;
  84.         for (int i = 0; i < 26; i++){
  85.             if(c[i] > 0){
  86.                 arrangement = (arrangement * invfact[c[i]]) % MOD;
  87.             }
  88.         }
  89.  
  90.         ll ans = (waysPartition * arrangement) % MOD;
  91.         cout << ans % MOD << "\n";
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.02s 12872KB
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/9Iw1Ng
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!