题目链接

题目链接

题目大意

题目的意思是把字符串删去连续的两个字母，问剩下的字符串拼起来有多少种？

题解

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007, P = 13331;
const int N = 2e5 + 10;

ull h[N], p[N];

ull get_hash(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    s = ' ' + s;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    unordered_set<ull> q;
    for (int i = 1; i <= n; i++) {
        if (i == 1)
            q.insert(get_hash(i + 2, n));
        else if (i == n)
            q.insert(get_hash(1, n - 2));
        else
            q.insert(get_hash(i + 2, n) + get_hash(1, i - 1) * p[n - i - 1]);
    }
    cout << q.size() << endl;
}
int main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}