T1: Problema de entrada

Este es un problema simple de verificación. Basta con usar un mapa (map) para contar las ocurrencias de elementos únicos.

#ifdef ONLINE_JUDGE 
#else 
#define Qiu_Cheng 
#endif 
#include <bits/stdc++.h>
#define int long long
#define fuck inline
using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

fuck int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c - '0');
        c = getchar();
    }
    return x * f;
}

fuck void solve() {
    int n;
    cin >> n;
    vector<int> nums(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
    }

    map<int, int> groups;
    int current_group = 1;

    for (int i = 1; i <= n; ++i) {
        if (groups[nums[i]] == 0) {
            groups[nums[i]] = current_group;
        } else {
            if (groups[nums[i]] != current_group) {
                ++current_group;
                groups[nums[i]] = current_group;
            }
        }
    }

    cout << current_group << '\n';
}

signed main() {
#ifdef Qiu_Cheng
    freopen("cul.in", "r", stdin);
    freopen("cul.out", "w", stdout);
#endif
    int t = read();
    while (t--) solve();
    return 0;
}

T2: Divisibilidad y eliminación de dígitos

El objetivo es determinar si se puede eliminar exactamente K dígitos de un número dado de forma que el número resultante sea divisible por 3, sin generar ceros a la izquierda.

Clave del razonamiento:

• Los dígitos se clasifican según su valor módulo 3: clase 0 (divisibles por 3), clase 1 (resto 1), clase 2 (resto 2).
• La suma total de los dígitos módulo 3 debe ser 0 para que el número final sea divisible por 3.
• Se busca una combinación de eliminaciones que cumpla con la congruencia y evite ceros iniciales.

Se aplica una estrategia de greedy: eliminar primero los dígitos no nulos desde el final, y luego ceros desde el inicio si es necesario.

#ifdef ONLINE_JUDGE 
#else 
#define Qiu_Cheng 
#endif 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e3 + 5;
const int mod = 1e9 + 7;

fuck int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c - '0');
        c = getchar();
    }
    return x * f;
}

string s;
int cnt[3];

fuck void solve() {
    int n, k;
    cin >> n >> k >> s;
    s = ' ' + s;

    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; ++i) {
        cnt[(s[i] - '0') % 3]++;
    }

    int target_mod = (cnt[1] + 2 * cnt[2]) % 3;

    // Casos especiales
    if (k == n || (k == n - 1 && cnt[0])) {
        cout << "yes\n";
        return;
    }
    if (k == 0) {
        cout << (target_mod ? "no" : "yes") << '\n';
        return;
    }

    int zeros_before_first_nonzero = 0;
    bool has_mod1_in_prefix = false;
    bool has_mod2_in_prefix = false;

    for (int i = 1; i <= n; ++i) {
        if (s[i] == '0') zeros_before_first_nonzero++;
        else if ((s[i] - '0') % 3 == 0) break;
    }

    for (int i = 1; i <= n; ++i) {
        if (s[i] == '0') break;
        if ((s[i] - '0') % 3 == 1) has_mod1_in_prefix = true;
        if ((s[i] - '0') % 3 == 2) has_mod2_in_prefix = true;
    }

    for (int k2 = 0; k2 <= cnt[2] && k2 <= k; ++k2) {
        int needed_mod1 = (target_mod - 2 * k2) % 3;
        if (needed_mod1 < 0) needed_mod1 += 3;

        for (int k1 = needed_mod1; k1 <= cnt[1] && k1 + k2 <= k; k1 += 3) {
            int k0 = k - k1 - k2;
            if (k0 < 0 || k0 > cnt[0]) continue;

            if (k0 >= zeros_before_first_nonzero ||
                (k1 < cnt[1] && has_mod1_in_prefix) ||
                (k2 < cnt[2] && has_mod2_in_prefix)) {
                cout << "yes\n";
                return;
            }
        }
    }

    cout << "no\n";
}

signed main() {
#ifdef Qiu_Cheng
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    int t = read();
    while (t--) solve();
    return 0;
}

T3: Permutaciones cíclicas y conteo con módulo

Se da una transformación de letras (a-z) en otras letras mediante una función f. Cada letra tiene un ciclo asociado. El objetivo es calcular cuántas formas existen de aplicar esta transformación múltiples veces de forma que todas las letras regresen a sí mismas después de n pasos, considerando que cada letra sigue su propio ciclo.

Observaciones clave:

• Cada letra pertenece a un ciclo cuya longitud es al máximo 6 (porque 1+2+3+4+5+6 > 26).
• Se agrupan las letras por longitud de ciclo.
• Usamos el principio de inclusión-exclusión para contar configuraciones válidas donde cada grupo de ciclos contribuye al resultado.
• Finalmente, calculamos el mínimo común múltiplo (LCM) de los ciclos seleccionados para obtener el periodo global.

#ifdef ONLINE_JUDGE 
#else 
#define Qiu_Cheng 
#endif 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c - '0');
        c = getchar();
    }
    return x * f;
}

vector<pair<int, int>> cycles;
char mapping[30];
bool visited[30];

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

void process_cycles() {
    cycles.clear();
    memset(visited, 0, sizeof(visited));

    for (int i = 1; i <= 26; ++i) {
        if (!visited[i]) {
            int len = 1;
            int cur = i;
            while (mapping[cur] != i) {
                cur = mapping[cur];
                visited[cur] = true;
                len++;
            }
            cycles.push_back({len, 1});
        }
    }

    // Combinar ciclos del mismo tamaño
    map<int, int> count;
    for (auto &p : cycles) {
        count[p.first]++;
    }
    cycles.clear();
    for (auto &p : count) {
        cycles.push_back(p);
    }
}

ll power(ll base, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

ll inclusion_exclusion(const vector<int>& choices, int n) {
    ll total = 0;
    int sz = choices.size();
    for (int mask = 1; mask < (1 << sz); ++mask) {
        ll sum = 0;
        int cnt = 0;
        for (int i = 0; i < sz; ++i) {
            if (mask & (1 << i)) {
                sum += choices[i];
                cnt++;
            }
        }
        ll term = power(sum, n);
        if (cnt % 2 == 1) {
            total = (total + term) % MOD;
        } else {
            total = (total - term + MOD) % MOD;
        }
    }
    return total;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= 26; ++i) {
        cin >> mapping[i];
        mapping[i] -= 'a';
        mapping[i] += 1;
    }

    process_cycles();

    ll ans = 0;
    int total = cycles.size();

    for (int mask = 1; mask < (1 << total); ++mask) {
        ll current_lcm = 1;
        vector<int> choices;
        for (int i = 0; i < total; ++i) {
            if (mask & (1 << i)) {
                int cycle_len = cycles[i].first;
                int count = cycles[i].second;
                current_lcm = lcm(current_lcm, cycle_len);
                choices.push_back(cycle_len * count);
            }
        }

        if (choices.size() > n) continue;

        ll ways = inclusion_exclusion(choices, n);
        ans = (ans + current_lcm * ways) % MOD;
    }

    cout << ans << '\n';
}

signed main() {
#ifdef Qiu_Cheng
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    int t = read();
    while (t--) solve();
    return 0;
}