Ta dùng mảng tổng tiền tố để có thể tính số lượng chữ cái mỗi loại trong đoạn từ ~l~ đến ~r~. Gọi ~cnt_{i, c}~ là tổng số lượng chữ cái ~c~ trong đoạn từ ~1~ đến ~i~, số lượng chữ cái ~c~ trong đoạn từ ~l~ đến ~r~ bằng ~cnt_{r, c} - cnt_{l-1,c }~.

Nếu với mọi chữ cái ~c~ từ 'a' đến 'z' trong đoạn từ ~l~ đến ~r~ đều có số lượng chẵn, ta có thể tạo palindrome với độ dài tối đa bằng ~r-l+1~ bằng cách chia đôi số lượng chữ cái mỗi loại, tạo ra một xâu bất kì có độ dài ~\frac{r-l+1}{2}~ với những chữ cái đã cho và lấy đối xứng sang bên phải. Gọi ~cur_c~ là số lượng chữ cái loại ~c~, khi đó số lượng xâu có thể tạo ra bằng = ~\frac{((r - l + 1) / 2)!}{(cur_a/2)! \cdot (cur_b/2)! ... (cur_z/2)!}~. Để có thể tính phép tính này, ta cần dùng nghịch đảo modulo.

Nếu trong đoạn từ ~l~ đến ~r~ tồn tại chữ cái có số lượng lẻ, để xâu palindrome có độ dài tối đa, ta thấy rằng chỉ một kí tự được phép có số lượng lẻ, còn lại đều có số lượng chẵn. Dễ thấy kí tự có số lượng lẻ thì chắc chắn một kí tự loại này sẽ phải ở chính giữa xâu palindrome, khi đó số lượng cách sẽ được tính giống như số lượng cách của bài toán mọi kí tự đều có số lượng chẵn. Số lượng xâu tạo được = (số lượng kí tự có số lượng lẻ) ~\times~ (số lượng xâu tạo được nếu mọi kí tự đều có số lượng chẵn sau khi bớt các kí tự lẻ đi ~1~ kí tự).

Độ phức tạp: ~O((n+q)\cdot26)~.

Code mẫu

#include <bits/stdc++.h>
#define fi(i,a,b) for(int i=a;i<=b;i++)
#define fid(i,a,b) for(int i=a;i>=b;i--)
#define getbit(x,i) ((x>>i)&1)
#define pii pair<int,int>
#define ll long long
#define TunaNgoo "maxpalindromes"
#define maxn 1000005
using namespace std;
const int mo = 1e9 + 7;
int n, q;
ll fact[maxn], rfact[maxn];
string s;
int f[maxn][26];
int power(int a, int b) {
    if(b == 0) return 1;
    ll c = power(a, b / 2);
    c = (c * c) % mo;
    if(b % 2) c = (c * a) % mo;
    return c;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    if(fopen(TunaNgoo".inp", "r")) {
        freopen(TunaNgoo".inp", "r", stdin);
        freopen(TunaNgoo".out", "w", stdout);
    }

    fact[0] = 1;
    for(int i = 1; i <= 1e5; i++) fact[i] = (fact[i - 1] * i) % mo;
    rfact[int(1e5)] = power(fact[int(1e5)], mo - 2);
    for(int i = 1e5; i >= 1; i--) rfact[i - 1] = (rfact[i] * i) % mo;

    cin >> s;
    n = s.length();
    s = ' ' + s;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 26; j++) f[i][j] = f[i - 1][j];
        f[i][s[i] - 'a']++;
    }
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        ll res = 1;
        int sum = 0, odd = 0;
        for(int i = 0; i < 26; i++) {
            int cnt = f[r][i] - f[l - 1][i];
            sum += cnt / 2;
            res = (res * rfact[cnt / 2]) % mo;
            odd += cnt % 2;
        }
        res = (res * fact[sum]) % mo;
        res = (res * max(1, odd)) % mo;
        cout << res << '\n';
    }
}