Merkkijonot

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

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

    ll i, j, k, l, a, b, sa = 0, sb = 0, ca, cb, ans = 0;
    ll n[2];
    string s;
    map <pl, ll> mp[2];
    vpl p[2];
    vpl x[2];
    cin >> n[0];
    n[1] = n[0]/2;
    n[0] -= n[1];

    for(k = 0; k < 2; k++)
    {
        for(i = 0; i < n[k]; i++)
        {
            a = b = 0;
            cin >> s;
            l = s.length();
            for(j = 0; j < l; j++)
                if(s[j] == 'a')
                    a++;
                else
                    b++;
            p[k].push_back({a, b});
            sa += a;
            sb += b;
        }
        n[k] = (1 << n[k]);
    }

    /*for(auto [v, d] : p[1])
        cout << v << " " << d << "\n";
    cout << "\n";
    for(auto [v, d] : p[0])
        cout << v << " " << d << "\n";
    cout << "\n";*/

    if(sa % 2 != 0 || sb % 2 != 0)
    {
        cout << 0;
        return 0;
    }

    sa /= 2;
    sb /= 2;

    for(k = 0; k < 2; k++)
    {
        for(i = 0; i < n[k]; i++)
        {
            j = ca = cb = 0;
            while((1 << j) <= i)
            {
                if((1 << j) & i)
                {
                    ca += p[k][j].first;
                    cb += p[k][j].second;
                }
                j++;
            }
            if(ca <= sa && cb <= sb)
            {
                mp[k][{ca, cb}]++;
                if(mp[k][{ca, cb}] == 1)
                    x[k].push_back({ca, cb});
                //cout << ca << " " << cb << "\n";
            }
        }
        //cout << "\n";
    }
    l = x[0].size();
    for(i = 0; i < l; i++)
    {
        a = x[0][i].first;
        b = x[0][i].second;
        ans += mp[0][{a, b}] * mp[1][{sa - a, sb - b}];
        //cout << a << " " << b << " " << mp[0][{a, b}] << " " << mp[1][{sa - a, sb - b}] << "\n";
        ans %= modd;
    }
    cout << ans;
    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: WRONG ANSWER

Test 9

Group: 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: WRONG ANSWER

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED