原题链接

一句话题解

由于t必须要包含非a字符，所以假如t包含前k个非a字符，那么s所包含的非a字符数量一定是k的倍数

实施

遍历t能包含几个非a字符，然后再算有几种填充a的方法
复杂度 \(logn·n\)
之所以有logn是因为遍历s包含的非a字符数量的因子

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x) {
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

ll solve() {
    string s;
    cin >> s;
    ll n = s.length();
    s = ' ' + s;
    vector<ll> p;
    for(ll i = 1; s[i]; i++) if(s[i] != 'a') p.push_back(i);

    ll num = p.size();
    if(!num) return n - 1;
    ll ans = 0;

    for(ll len = 1; len <= num; len++) {
        if(num % len) continue;
        bool flag = 1;
        for(ll i = len; i < num; i++) {
            if(s[p[i]] != s[p[i-len]]) {
                flag = 0;
                break;
            }
            if(i % len && p[i] - p[i-1] != p[i-len] - p[i-len-1]) {
                flag = 0;
                break;
            }
        }

        if(flag) {
            ll pregap = p[0] - 1, sufgap = n - p[num-1];
            for(ll i = len; i < num; i += len) {
                sufgap = min(sufgap, p[i] - p[i-1] - 1);
            }
            for(ll i = 0; i <= sufgap; i++) {
                ans++;
                if(sufgap - i > 0) ans += min(pregap, sufgap - i);
            }
            //printf("len:%d  ans:%d\n",len,ans);
        }
    }
    return ans;
}

int main() {
    ll t;
    read(t);
    while(t--) {
        write(solve());
        putchar('\n');
    }
    return 0;
}