Competitive Programming using Claude 4

index.cpp

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 998244353;
static const int MAXN = 500000;

long long modexp(long long a, long long e = MOD-2) {
    long long r = 1;
    while(e) {
        if(e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Precompute factorials and inverse factorials up to MAXN
    static long long fact[MAXN+1], invfact[MAXN+1];
    fact[0] = 1;
    for(int i = 1; i <= MAXN; i++)
        fact[i] = fact[i-1] * i % MOD;
    invfact[MAXN] = modexp(fact[MAXN]);
    for(int i = MAXN; i > 0; i--)
        invfact[i-1] = invfact[i] * i % MOD;

    int t;
    cin >> t;
    while(t--) {
        vector<int> c(26);
        long long n = 0;
        for(int i = 0; i < 26; i++){
            cin >> c[i];
            n += c[i];
        }
        // Number of odd positions and even positions
        int O = (n + 1) / 2;
        int E = n / 2;

        // Compute F = O! * E! / ( ∏_{i} c[i]! )  mod
        long long F = fact[O] * fact[E] % MOD;
        for(int i = 0; i < 26; i++){
            F = F * invfact[c[i]] % MOD;
        }

        // Build knapsack dp over only those letters with c[i]>0
        // dp[s] = #ways to pick a subset of these letters summing to s
        vector<long long> dp(O+1, 0);
        dp[0] = 1;
        for(int i = 0; i < 26; i++){
            int w = c[i];
            if(w == 0) continue;
            // standard 0/1 knapsack downward update
            for(int s = O; s >= w; s--){
                dp[s] = (dp[s] + dp[s - w]) % MOD;
            }
        }

        // The count of valid assignments is dp[O].
        cout << (dp[O] * F) % MOD << "\\\\n";
    }

    return 0;
}