传送门

题意让求一个排列，字典序最大而且使得逆序对数量为k，再对这个序列按照每位乘上(n + 1) ^ i求和

第一点 : 字典序最大的排列方式肯定为9876 3 12 45这样的有四段，第一段是贪心地拿字典序最大的变成最多的逆序对，如9876 12345这样有 (5 + 8) * 4 / 2 = 26 个逆序对，如果需要28个逆序对，肯定是把 3 放在尽量前面 9876 3 12 45 ，这样就组成了四段，第一段9降序，第二段是3，第三段1升序，第四段从3 + 1升序。

接下来就变成了序列求和的问题。观察到\sum{p[i] * (n + 1)^{i}}实际上是一个公差为 1 或者 -1 的等差数列和公比为（n + 1）的等差数列相乘的来。

引理：对于首项为a_1，公差为d_1，的等差数列a_n，首项b_1，公比q的等比数列b_n。
一定存在S_n = \sum{a_i b_i} = x_1b_1 – x_{n + 1}b_{n + 1}
其中 x 为等差数列 x_1 = \frac{a_1}{1 – q}+\frac{qd}{(1-q)^2} \quad d_0=\frac{d}{1-q}

有了这个公式就可以直接对序列进行求和了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
ll get(ll x, ll y)
{
    return (x + y) * (y - x + 1) / 2;
}
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = (res * n) % mod;
        n = (n * n) % mod;
        k >>= 1;
    }
    return res % mod;
}
ll sum(ll a1, ll d1, ll b1, ll q, ll n)
{
    if(n == 0) return 0;
    ll x1 = ((a1 % mod) * ksm(1 - q, mod - 2)) % mod + (((d1 * q) % mod) * ksm(((1 - q) * (1 - q)) % mod, mod - 2)) % mod;
    ll dx = (d1 * ksm(1 - q, mod - 2)) % mod;
    //cout << x1 << " " << dx << endl;
    ll xnp1 = ((x1 % mod) + (dx * n) % mod) % mod;
    ll bnp1 = (b1 * ksm(q, n)) % mod;
    return (((x1 * b1 - xnp1 * bnp1) % mod) + mod) % mod;
}
int main()
{
    ll n, k;
    cin >> n >> k;
    ll l = 0, r = n;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        if(get(n - mid, n - 1) <= k) l = mid + 1;
        else r = mid;
    }
    if(get(n - l, n - 1) > k) l -= 1;
    //cout << l;
    k -= get(n - l, n - 1); k++;
    //cout << k << endl; return 0;
    ll ans1 = sum(n, -1, n + 1, n + 1, l);

    ll ans2 = k * ksm(n + 1, l + 1);

    ll ans3 = sum(1, 1, ksm(n + 1, l + 2), n + 1, k - 1);

    ll ans4 = sum(k + 1, 1, ksm(n + 1, l + k + 1), n + 1, n - l - k);
    //cout << ans4 << endl;
    cout << (ans1 + ans2 + ans3 + ans4) % mod;
}