Merkkijonot

#include <bits/stdc++.h>

#define MODE 0

#if MODE == 1
#define debug(x) cout << #x << ": " << x << endl
#define log(x) cout << x << endl
#else
#define debug(x)
#define log(x)
#endif

#define M 1000000007

using namespace std;
using ll = long long;
using pii = pair<int, int>;

void solve() {
    int n;
    cin >> n;

    vector<pii> v(n, {0, 0});
    int acnt=0, bcnt=0;

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;

        for (char c: s) {
            if (c == 'a') {
                ++v[i].first;
                ++acnt;
            } else {
                ++v[i].second;
                ++bcnt;
            }
        }
    }

    if ((acnt&1) || (bcnt&1)) {
        cout << "0\n";
        return;
    }

    int agoal = acnt>>1;
    int bgoal = bcnt>>1;

    ll dp[agoal+1][bgoal+1];
    ll next[agoal+1][bgoal+1];

    memset(dp, 0, sizeof(dp));
    memset(next, 0, sizeof(next));

    dp[0][0] = 1;

    int anow = 0;
    int bnow = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= anow && j <= agoal; ++j) {
            for (int k = 0; k <= bnow && k <= bgoal; ++k) {
                next[j][k] = (next[j][k] + dp[j][k]) % M;
                if (j + v[i].first <= agoal && k + v[i].second <= bgoal) {
                    next[j + v[i].first][k + v[i].second] = (next[j + v[i].first][k + v[i].second] + dp[j][k]) % M;
                }
            }
        }

        copy(next[0], next[agoal]+bgoal+1, dp[0]);
        memset(next, 0, sizeof(next));
        anow += v[i].first;
        bnow += v[i].second;
    }

    cout << dp[agoal][bgoal] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("input.txt", "r", stdin);

    solve();
    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED