题目

link

分析

首先因为 , 枚举每一种情况求和是不可能的。

我们枚举一下 的情况:

这时我们发现, 将 的所有序列按照字典序排序后, 将前 种排列的后三位离散化, 就是 时的所有情况情况. 假设我们已经知道了 时的答案, 且知道新增加的数是如何影响逆序对个数的, 我们就可以用递推解出此题.

显然的, 在一个序列前添加一个数, 增加的逆序对的数量是其后方比其小的数的个数. 具体地, 在上面的例子中, 当这个数是 的时候, 增加的数量为 ; 当这个数是 时, 增加的数量为零; 当这个数是 时, 增加是数是 .

设 为任意一个长度为 的排列, 为任意一个长度为 的排列, 则:

定义 是 时的答案, 则我们知道:

其中 是题目给定的模数. 我们只需要提前处理出 的次幂, 就可以快速的得出答案.

代码

#include <iostream>

using std::cin;
using std::cout;

const long long MOD = 1e9 + 7;
long long n;
long long pwr[10000005], f[10000005];

void init()
{
    pwr[0] = 1;
    pwr[1] = 2;
    for (int i = 2; i <= 10000005; ++i)
    {
        pwr[i] = pwr[i - 1] * 2 % MOD;
    }

    return;
}

long long solve(int x)
{
    f[1] = 1;
    f[2] = 3;
    for (int i = 3; i <= x; ++i)
    {
        f[i] = f[i - 1] * (pwr[i] - 1) % MOD;
    }
    return f[x];
}

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    std::ios::sync_with_stdio(false);

    init();
    cin >> n;
    cout << solve(n);

    return 0;
}