Merkkijonot

input/code.cpp: In function 'pl cvt(std::string)':
input/code.cpp:16:22: warning: unused variable 'i' [-Wunused-variable]
   16 |     ll a = 0, b = 0, i;
      |                      ^

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pl;
typedef vector <ll> vl;
typedef vector <pl> vpl;
typedef vector <vl> vvl;
const ll modd = 1e9 + 7;

#define fi first
#define se second
#define pb push_back

pl cvt(string s)
{
    ll a = 0, b = 0, i;
    for(auto x : s)
        if(x == 'a')
            a++;
        else
            b++;
    return {a, b};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    ll n, i, j, x = 0, y = 0, c = 0;
    string s;
    cin >> n;
    vpl a(n + 1);
    for(i = 1; i <= n; i++)
    {
        cin >> s;
        a[i] = cvt(s);
        x += a[i].fi;
        y += a[i].se;
    }

    if(x % 2 != 0 || y % 2 != 0)
    {
        cout << 0;
        return 0;
    }

    x /= 2, y /= 2;
    map <pl, ll> mp;
    for(i = 0; i <= x; i++)
        for(j = 0; j <= y; j++)
        {
            mp[{i, j}] = c;
            c++;
        }

    vvl ks(n + 1, vl(c + 1, 0));
    ks[0][0] = 1;

    for(i = 1; i <= n; i++)
    {
        ll k = mp[a[i]];
        for(j = c - 1; j >= k; j--)
        {
            ks[i][j] += ks[i - 1][j] + ks[i - 1][j - k];
            ks[i][j] %= modd;
        }
        for(j = k - 1; j >= 0; j--)
            ks[i][j] = ks[i - 1][j];
    }

    /*for(i = 0; i <= n; i++)
    {
        for(j = 0; j <= c; j++)
            cerr << ks[i][j] << " ";
        cerr << "\n";
    }*/


    cout << ks[n][mp[{x, y}]];
    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