P5770 [JSOI2016] 无界单词 题解

namespace lowspeed_song {

int n;
char s[N];
u64 f[N], g[N], pwr[N];

inline void init() {
    pwr[0] = 1;
    for (int i = 1; i <= 63; ++i) pwr[i] = pwr[i - 1] * 2;
    for (int i = 1; i <= 64; ++i) {
        f[i] = pwr[i];
        for (int j = 1; j + j <= i; ++j) f[i] -= f[j] * pwr[i - j - j];
    }
}

inline int same(int l1, int r1, int l2) {
    for (int i = 0; i <= r1 - l1; ++i)
        if (s[l1 + i] != s[l2 + i]) return 0;
    return 1;
}

inline int good(int len) {
    for (int i = 1; i <= len / 2; ++i)
        if (same(1, i, len - i + 1)) return 0;
    return 1;
}

inline u64 calc(int len) {
    for (int i = 1; i <= n; ++i) {
        if (i <= len) g[i] = good(i);
        else {
            g[i] = pwr[i - len];
            for (int j = 1; j <= i / 2; ++j)
                if (j <= i - len) g[i] -= g[j] * pwr[i - j - max(len, j)];
                else if (same(1, len - i + j, i - j + 1)) g[i] -= g[j];
        }
    } return g[n];
}

inline void sol() {
    u64 k; cin >> n >> k;
    cout << f[n] << '\n';
    for (int i = 1; i <= n; ++i) {
        s[i] = 'a';
        u64 cnt = calc(i);
        if (cnt < k) k -= cnt, cout.put('b'), s[i] = 'b';
        else cout.put('a'), s[i] = 'a';
    } cout << '\n';
}

} // namespace lowspeed_song