Merkkijonot

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
const ll M = 1e9 + 7;
const int of = 250;
vector<pair<int, int>> v;
 
map<pair<int, pair<pair<int, int>, pair<int, int>>>, bool> vis;
map<pair<int, pair<pair<int, int>, pair<int, int>>>, int> dp;
 
 
int n;
int atot = 0;
int btot = 0;
 
ll cnt(int i, pair<int, int> x, pair<int, int> y) {
    if (i == n) {
        //cout << x.first << " " << x.second << " " << y.first << " " << y.second << endl;
        return x == y;
    }
 
    if (x.first > atot / 2 || y.first > atot / 2) return 0;
    if (x.second > btot / 2 || y.second > btot / 2) return 0;
 
    if (vis[{i, {x, y}}]) {
        return dp[{i, {x, y}}];
    }
 
    ll a = 0;
 
    a += cnt(i + 1, {x.first + v[i].first, x.second + v[i].second}, y);
    a += cnt(i + 1, x, {y.first + v[i].first, y.second + v[i].second});
 
    a = a % M;
 
    vis[{i, {x, y}}] = 1;
    dp[{i, {x, y}}] = a;
 
    return a;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
 
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int a = 0;
        int b = 0;
        for (int j = 0; j < (int)s.size(); ++j) {
            if (s[j] == 'a') a++;
            else b++;
        }
 
        v.push_back({a, b});
        atot += a;
        btot += b;
        //cout << a << " " << b << endl;
    }
 
    sort(v.rbegin(), v.rend());
 
    cout << cnt(0, {0, 0}, {0, 0}) << "\n";
 
    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