Merkkijonot

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
 
const ll mod = (ll)1e9 + 7;
 
const int N = 500;
 
ll dp[N+1][251][251];
 
 
 
int main(){
 
    int n;
    cin >> n;
    vector<string> words(n+1);
    words[0] = "#";
    int sum =0;
    for(int i = 1; i <= n; ++i){
        cin>>words[i];
        sum += (int)words[i].size();
    }    
 
    if(sum%2){
        cout << "0\n";
        return 0;
    }
 
    vector<int> cnt(n+1);
    int tot_cnt = 0;
    for(int i = 1; i <= n; ++i){
        for(char c : words[i]){
            if(c=='a'){
                cnt[i]++;
                tot_cnt++;
            }
        }
    }
 
    if(tot_cnt%2){
        cout << "0\n";
        return 0;
    }
 
  
    dp[0][0][0] = 1;
 
    for(int i = 1; i <= n; ++i){
        for(int s = 0; s <= sum/2; ++s){
            for(int a = 0; a <= tot_cnt/2; ++a){
                dp[i][s][a] = dp[i-1][s][a];
                if(s-(int)words[i].size() >= 0 && a-cnt[i] >= 0){
                    dp[i][s][a] += dp[i-1][s-(int)words[i].size()][a-cnt[i]];
                }
                dp[i][s][a] %= mod;
            }
        }
    }
 
    cout << dp[n][sum/2][tot_cnt/2] << "\n";
 
    // we want that both
    // sets have the same number of total characters
    // and the same number of a's
    // first solve the problem
    // of just creating two sets with equal size:
    // maximum 500 chars in total
    // meaning that both sides
    // have max 250 chars
    // meaning what?
    // we can go through each number of a's (0 to 250)
    // go through 
    // dp[i], amount of ways until i
    // dp[0] = 0
    // dp[1] = 
    // how was two sets solved?
    // dp[i][sum][num of a's] tells how many ways there are to create set 
    // of size sum with specific num of a's
    // dp[0] = 1
    // dp[1] = 0
    // dp[2][s][a] = dp[1][s-words[i].size()][a-cnt[i]]
 
 
 
 
 
 
}

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