\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

• Thử từng dãy hoán vị một và tính kết quả theo cách đề bài đã nêu

Độ phức tạp: \(O(n! \times n^2)\) thời gian và \(O(n)\) bộ nhớ

• Để optimize thêm một tí bạn có thể dọc bài này (Code mẫu)

Độ phức tạp: \(O((n! \times n + n) \log_2 n)\) thời gian và \(O(n)\) bộ nhớ

\(\color{#300000}{\text{Hint 2 <Tiền xử lí> <Toán học>}}\)

Đầu tiên, cần đơn giản hóa biểu thức cần tính toán. Với mỗi hoán vị \(p\), ta định nghĩa \(l_i\) là số lượng \(j < i\) và \(p_j < p_i\). Khi đó \(F(p) = l_1p_1 + l_2p_2 + ... + l_np_n\). Đến đây có hai hướng giải:

\(\color{#601515}{\text{Giải bằng quy hoạch động:}}\)

• Gọi \(d[n]\) là đáp án cần tìm cho \(n\).

• Một kỹ thuật quen thuộc khi gặp các bài dạng hoán vị như thế này là chú ý là vào vị trí các phần tử đặt biệt như \(1\) hoặc \(n\) (Cụ thể bài này ta sẽ chú ý vị trí của \(n\))

• Gọi \(p_i = n\), ta có \(i - 1\) số \(p_j \in [0, n) < n\) với \(j \in [0, i)\)

  Khi đó \(l_i = i - 1\)

• Đồng thời sau khi bỏ \(n\) ra, ta còn lại một hoán vị \(p'\) có \(n - 1\) số và \(n\) không đóng góp vào bất cứ \(l_j\) nào nữa.

  Khi đó \(F(p) = n * (i - 1) + F(p')\).

• Vì \(p'\) có thể là một hoán vị độ dài \(n - 1\) bất kỳ

  Khi đó tổng của tất cả \(F(p)\) mà \(p_i = n\) là \(d[n - 1] + n * (i - 1) * (n - 1)! = d[n - 1] + n! * (i - 1)\).

• Tổng hết tất cả \(i\) từ \(1\) đến \(n\) ta thu được kết quả bài toán \(d[n]\)

  \(d[n] = n * d[n - 1] + n! * (0 + 1 + 2 + ... + n - 1) = n * d[n - 1] + \dfrac{n! * n * (n - 1)}{2}\).

\(\color{#601515}{\text{Giải bằng toán học:}}\)

• Đầu tiên, nhìn vào điều kiện \(j < i\) và \(p_j < p_i\), ta liên tưởng đến một thuận thế.

Với mỗi thuận thế như vậy, đáp số sẽ được cộng lên \(p_i\).

Ta sẽ thử cố định một thuận thế bất kỳ và xem nó xuất hiện trong bao nhiêu hoán vị.

• Xét trong bài toán nhỏ, khi \(n = 3\)

Thuận thế \((1, 2)\) sẽ xuất hiện trong \(3\) hoán vị \([1, 2, 3], [1, 3, 2], [3, 1, 2]\).

Một cách tổng quát, mỗi thuận thế \((a, b)\) với \(a < b\) sẽ xuất hiện trong đúng \(\dfrac{n!}{2}\) hoán vị (nửa số hoán vị còn lại \(b\) sẽ đứng trước \(a\)).

Như vậy kết quả bài toán là \(res = \displaystyle \dfrac{n!}{2} \sum_{i=1}^n \sum_{j = i + 1}^n j\)

• Tổng này cần tính trong hai vòng for dẫn tới việc chạy quá thời gian, vì vậy ta thử rút gọn nó một chút như sau.

$\displaystyle
\begin{align}
\sum_{i=1}^n \sum_{j = i + 1}^n j &= \sum_{i=1}^n \left[ \frac{n(n + 1)}{2} - \frac{i(i + 1)}{2} \right] = \frac{n^2(n+1)}{2} - \frac{1}{2} \sum_{i=1}^n i^2 - \frac{1}{2} \sum_{i=1}^n i \
&= \frac{n^2(n+1)}{2} - \frac{n(n+1)(2n+1)}{12} - \frac{n(n+1)}{4} = ... = \frac{(n - 1)n(n + 1)}{3}
\end{align}
$

• Từ đó ta suy ra công thức của bài toán là \(res = \frac{n!}{2} \times \frac{(n - 1)n(n + 1)}{3}\)

• Vì không có phép chia modulo nên ta phải cẩn thận

hoặc là nghịch đảo modulo (có số modulo nguyên tố)

\(res = n! \times (n - 1)n(n + 1) \times inverse(6) = n! \times (n - 1)n(n + 1) \times 6^{10^9 + 5} \pmod{10^9 + 7}\)

hoặc là chia nó trước khi dùng modulo

\(res = (\frac{(n + 1)!}{3}\ mod\ (10^9 + 7)) \times (\frac{n \times (n + 1)}{2}\ mod\ (10^9 + 7)) \pmod{10^9 + 7}\)

• Và đê tránh phải tính lại, chúng ta có thể dùng quy hoạch động hoặc tiền xử lí để trả lời truy vấn nhanh hơn

\(\color{#009933}{\text{Preference AC Code }}\): Tiền xử lí, toán học

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(q + lim)\ \color{#7f5f3f}{\text{time}}\ ||\ O(lim)\ \color{#7f5f3f}{\text{memory}}}}\)

const int MOD = 1e9 + 7;
const int lim = 1e6 + 10;
int main()
{
    vector<int> a(lim + 1);
    vector<int> p(lim + 1);
    a[0] = 0;       p[0] = 1;
    a[1] = 0;       p[1] = 1;
    a[2] = 2;       p[2] = 2;
    a[3] = 24;      p[3] = 6 / 3;  /// da chia 3 truoc khi modulo
    a[4] = 240;     p[4] = 24 / 3; /// da chia 3 truoc khi modulo
    for (int n = 5; n <= lim; ++n)
        p[n] = (1LL * p[n - 1] * n) % MOD;

    for (int n = 5; n <= lim; ++n)
    {
        int v = (ll(n) * (n - 1) / 2) % MOD; /// da chia 2 truoc khi modulo
        a[n] = (1LL * p[n + 1] * v) % MOD;
    }

    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        cout << a[n] << '\n';
    }
    return 0;
}

\(\color{#c01515}{\text{<Giải trực tiếp> và <Lan truyền lười nhác>}}\)

• Bài này có thể giải với độ phức tạp \(O(max\_val)\) thời gian và bộ nhớ tiền xử lí nhưng vẫn giữ \(O(q)\) thời gian truy vấn với \(O(1)\) bộ nhớ

\(\color{#009933}{\text{Preference AC Code }}\): Giải trực tiếp, Lan truyền lười nhác || Online Solving, Lazy Solving

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(q + lim)\ \color{#7f5f3f}{\text{time}}\ ||\ O(lim)\ \color{#7f5f3f}{\text{memory}}}}\)

vector<int> a = {0, 0, 2, 24, 240}; /// a[0..5)
int f = 1 * 2 * 3 * 4 * 5 / 3;      /// 5! / 3
void lazy(int cur)
{
    for (int i = a.size(); i <= cur; ++i)
    {
            f = (1LL * f * (i + 1)) % MOD;     ///    p = (n + 1)! / 3
        int v = (1LL * i * (i - 1) / 2) % MOD; ///    v = n * (n - 1) / 2
        a.push_back((1LL * f * v) % MOD);      /// a[n] = p * v (mod MOD)
    }
}

int main()
{
    int q;
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        if (x >= a.size()) lazy(x);
        cout << a[x] << eol;
    }
    return 0;
}