GFOI Round 2 Strings 题解

设 f_i 为存在一个偶回文前缀的序列个数。有转移：

答案即为

可以用 CF1864H 第一篇题解的做法 在 O(\log^4 n) 时间内求出单个 f_n，大概就是矩阵维护 f_{\left\lfloor\frac{i}{2^k}\right\rfloor} 和 m^{\left\lfloor\frac{i}{2^k}\right\rfloor} 的转移。

考虑如何求答案式子。枚举 2 \left\lfloor\frac{i}{3}\right\rfloor，相当于要求一个类似于 \sum\limits_{i = 1}^N [i \bmod 2 = 0] f_i (m^{\frac{i}{2}} + m^{\frac{i}{2} + 1} + m^{\frac{i}{2} + 2}) 的东西。提出 1 + m + m^2 后变成 \sum\limits_{i = 1}^N [i \bmod 2 = 0] f_i m^{\frac{i}{2}} = m^{\frac{N}{2}} \sum f_i (m^{-1})^{\frac{N}{2} - \frac{i}{2}}。这玩意可以用一个变量 ans 维护，当 i \bmod 2 = 0 时让 ans \gets m^{-1} ans + f_i 即可。

时间复杂度 O(T \log^4 n)。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef __uint128_t u128;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 122;
const ll mod = 1000000007;

inline ll qpow(ll b, ll p) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            res = res * b % mod;
        }
        b = b * b % mod;
        p >>= 1;
    }
    return res;
}

ll n, m;
struct mat {
    ll a[maxn][maxn];
    mat() {
        mems(a, 0);
    }
} F[maxn], G[maxn], H[maxn];

inline mat operator * (const mat &a, const mat &b) {
    mat res;
    for (int i = 0; i < maxn; ++i) {
        for (int j = 0; j < maxn; ++j) {
            u128 x = 0;
            for (int k = 0; k < maxn; ++k) {
                x += a.a[i][k] * b.a[k][j];
            }
            res.a[i][j] = x % mod;
        }
    }
    return res;
}

struct vec {
    ll a[maxn];
    vec() {
        mems(a, 0);
    }
};

inline vec operator * (const vec &a, const mat &b) {
    vec res;
    for (int i = 0; i < maxn; ++i) {
        for (int j = 0; j < maxn; ++j) {
            res.a[j] = (res.a[j] + a.a[i] * b.a[i][j]) % mod;
        }
    }
    return res;
}

inline ll calc(ll n) {
    vec ans;
    for (int i = 60; i < 120; ++i) {
        ans.a[i] = 1;
    }
    for (int i = 59; ~i; --i) {
        if (n & (1LL << i)) {
            ans = ans * G[i];
        }
    }
    return ans.a[0];
}

void solve() {
    scanf("%lld%lld", &n, &m);
    m %= mod;
    if (!m) {
        puts("0");
        return;
    }
    ll im = qpow(m, mod - 2);
    for (int l = 0; l < 60; ++l) {
        F[l] = mat();
        for (int i = 0; i <= 120; ++i) {
            F[l].a[i][i] = 1;
        }
        for (int i = 0; i <= l; ++i) {
            if (i < l) {
                F[l].a[i + 60][i + 60] = m;
            }
            for (int j = i; j < l; ++j) {
                F[l].a[j][i] = F[l].a[j + 60][i] = m * (((j - i) & 1) ? mod - 1 : 1) % mod;
            }
            F[l].a[l][i] = m * (((l - i) & 1) ? mod - 1 : 1) % mod;
        }
    }
    F[0].a[0][120] = 1;
    F[0].a[120][120] = im;
    G[0] = H[0] = F[0];
    for (int i = 1; i < 60; ++i) {
        G[i] = H[i - 1] * F[i];
        H[i] = G[i] * H[i - 1];
    }
    ll t = (n / 3 - 1) * 2 + 1, ans = 0;
    vec A;
    for (int i = 60; i < 120; ++i) {
        A.a[i] = 1;
    }
    for (int i = 59; ~i; --i) {
        if (t & (1LL << i)) {
            A = A * G[i];
        }
    }
    ans = (ans + A.a[120] * qpow(m, t / 2) % mod * (1 + m + m * m % mod)) % mod;
    t = calc(n / 3 * 2);
    for (ll i = n / 3 * 3; i <= n; ++i) {
        ans = (ans + t * qpow(m, i - i / 3 * 2)) % mod;
    }
    printf("%lld\n", ans);
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}