codes.cpp

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int MAXN = 1e6 + 10;
const int INF = 1e9 + 7;
const int EPS = 1e-6;

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
pair <string, int> a[MAXN];
int last1[MAXN], last2[MAXN];
int dp[MAXN];
void solve(){

    for (int i = 0; i < n; i++)
        dp[(1 << i)][i] = 1;

    for (int mask = 1; mask < (1 << n); mask++){
        for (int i = 0; i < n; i++){
            if (((mask >> i) & 1) == 1){
                for (int j = 0; j < n; j++){
                    if (((mask >> j) & 1) == 0 && abs(i - j) <= k){
                        dp[mask | (1 << j)][j] += dp[mask][i];
                    }
                }
            }
        }
    }


    for (int i = 2; i <= n; i++){
        for (int k = 1; k <= 2 * i; k++){
            for (int mask1 = 0; mask1 < 4; mask1++){
                for (int mask2 = 0; mask2 < 4; mask2++){
                    int add = check(mask1, mask2);
                    dp[i][k + add][mask2] += dp[i - 1][k][mask1];
                }
            }
        }
    }

    cin >> s;
    ma[s] = i;

    for (int mask = 0; mask < (1 << n); mask++){
        bool flag = false;
        for (int i = 1; i <= m; i++){
            int num1 = ma[x[i]];
            int num2 = ma[y[i]];
            if (((mask >> num1) & 1) && ((mask >> num2) & 1))
                flag = true;
        }
        if (!flag){
            int cnt = __builtin_popcount(mask);
            if (ans < cnt){
                ans = cnt;
                best_mask = mask;
            }
        }
    }


    int n, m;
    cin >> m >> n >> s;

    for (int i = 1; i < m; i++){
        cnt[s[i - 1] - 'a'][s[i] - 'a']++;
        cnt[s[i] - 'a'][s[i - 1] - 'a']++;
    }

    for (int mask = 0; mask < (1 << n); mask++){
        int pos = __builtin_popcont(mask) + 1;
        for (int i = 0; i < n; i++){
            if (((mask >> i) & 1) == 0){

                int sum = 0;
                for (int j = 0; j < n; j++){
                    if (i == j) continue;

                    if (((mask >> j) & 1) == 0){
                        sum -= pos * cnt[i][j];
                    }
                    else{
                        sum += pos * cnt[i][j];
                    }
                }
                dp[mask | (1 << j)] = min(dp[mask | (1 << j)],
                                          dp[mask] + sum);
            }
        }
    }
    cout << dp[(1 << n) - 1];


}
int main() {
    IOS;
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}