Subtask ~1, 2~: ~r \le 10~.

Subtask này có thể duyệt đơn thuần mọi xâu. Cần lưu ý rằng, vai trò của các ký tự là như nhau, nên ở subtask ~2~, ta cần duyệt có cận và khôn ngoan hơn để qua được.

Subtask ~4~: ~k = 1~.

Với subtask này, chỉ có duy nhất một xâu có độ dài ~i~, và tất cả đều là xâu đối xứng. Vậy kết quả là ~r - l + 1~.

Độ phức tạp: ~O~ (~1~).

Subtask ~6~: Không có ràng buộc gì thêm.

Ta sẽ coi như ta cần tính số lượng xâu đối xứng đôi với độ dài ~\le n~. Khi ta xây dựng hàm này, ta có thể lấy kết quả ~\le R~ trừ đi kết quả ~\le L - 1~.

Để tính số lượng đối xứng đôi có độ dài ~n~, ta tính một hàm phụ trợ ~R(n, k)~, là số cách để tạo một xâu độ dài ~n~ trên bảng chữ cái kích thước ~k~ dưới dạng nối của hai palindrome. Để làm điều đó, ta liệt kê độ dài của palindrome đầu tiên từ ~0~ đến ~n - 1~. Vì số lượng palindrome độ dài ~L~ trên bảng chữ cái kích thước ~k~ là ~k^{⌈L / 2⌉}~, ta thu được:

~R(n, k) = ∑_{L = 0}^{n - 1} k^{⌈L / 2⌉} ⋅ k^{⌈(n - L) / 2⌉}~

Tuy nhiên, với cách phân tích như vậy, một số đối xứng đôi sẽ được đếm hai lần, ví dụ như xâu "abacabacabac" có thể được biểu diễn như một cặp palindrome theo ba cách:

• aba|cabacabac
• abacab|acabac
• abacaba|cabac

Như vậy, ta đã đếm xâu này ba lần.

Chú ý rằng một xâu độ dài ~n~ là đối xứng đôi khi và chỉ khi nó bằng với một dịch vòng của nghịch đảo của chính nó, tức là tồn tại một số ~k~ (thực ra là độ dài của palindrome đầu tiên trong cách chia xâu ~s~) sao cho ~∀i: s_i = s_{k - 1 - i} mod n~.

Giả sử với xâu ~s~ có hai cách chia nó thành hai palindrome, trong đó độ dài của palindrome đầu tiên là ~l_1~ và ~l_2~ với ~l_1 < l_2~. Khi đó:

~s_i = s_{l_1 - 1 - i mod n} = s_{l_2 - 1 - i mod n}~

Tức là xâu ~s~ có tính chu kỳ với chu kỳ ~l_2 - l_1~, thậm chí là chu kỳ nhỏ hơn là ~gcd(n, l_2 - l_1)~. Gọi ~p~ là chu kỳ nhỏ nhất của đối xứng đôi ~s~, thì ~p~ cũng là chu kỳ của palindrome, và ~s~ được biểu diễn dưới dạng nối của không quá hai palindrome theo cách duy nhất. Khi đó trong ~R(n, k)~ ta đã đếm chính xác ~⌊s / p⌋~ lần.

Bây giờ ta tính giá trị ~D(n, k)~ — là số lượng đối xứng đôi độ dài ~n~ trên bảng chữ cái kích thước ~k~, được chia thành hai palindrome theo cách duy nhất. Với ~D(n, k)~, có công thức đệ quy sau:

~D(n, k) = R(n, k) - ∑_{l ∣ n, l < n} D(l, k)~

Khi đó, đáp án là:

~∑_{l ∣ n} ∑_{k} D(l, k)~

Độ phức tạp: ~O(n log n)~.

Code mẫu:

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

#define int long long
#define fi first
#define se second

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

int l, r, k, f[N], g[N], h[N];

vector <int> v[N];

void sieve (){
    for (int i = 1; i < N; i++) for (int j = 2 * i; j < N; j += i) v[j].push_back (i);
}

int up (int c){
    return c / 2 + (c % 2);
}

int POW (int a, int b, int p){
    a %= p;
    if (a == 0) return 0;
    int ret = 1;
    while (b > 0){
        if (b & 1){  
            ret = (ret * a) % p; b--;
        }
        a *= a; a %= p; b >>= 1;
    }
    return ret;
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    cin >> l >> r >> k;
    g[1] = k; g[2] = k * k;
    h[1] = k; h[2] = k * (k - 1);
    sieve ();   
    int cnt = 2;
    for (int i = 3; i <= r; i++){       
        g[i] = POW (k, up (i), mod);
        g[i] %= mod;

        if (i & 1){
            int c = up (i);
            g[i] += cnt * POW (k, c, mod);
            g[i] %= mod;
            cnt += 2;
        } else {
            int c = up (i);
            g[i] += (c - 1) * POW (k, c, mod);
            c++;
            g[i] += (c - 1) * POW (k, c, mod);
            g[i] %= mod;
        }

        int total = 0;

        for (int j : v[i]){
            g[i] -= (i / j - 1) * h[j];
            total += h[j];
        }

        g[i] %= mod; g[i] += mod; g[i] %= mod;

        h[i] = g[i] - total;

        h[i] %= mod; h[i] += mod; h[i] %= mod;
    }

    int res = 0;
    for (int i = l; i <= r; i++) res += g[i];
    cout << res % mod;
}