「题解」 P8474 立春

AtomAlpaca

题目
分析
代码

题目

分析

首先因为 $n \le 10^7$ , 枚举每一种情况求和是不可能的。

我们枚举一下 $n = 4$ 的情况: $\begin{aligned} \sum_{\sigma}{2 ^ {\tau \left( \sigma \right)}} &= 2^{\tau \left( < 1, 2, 3, 4 > \right)} \\ &+ 2^{\tau \left( < 1, 2, 4, 3 > \right)} \\ &+ 2^{\tau \left( < 1, 3, 2, 4 > \right)} \\ &+ 2^{\tau \left( < 1, 3, 4, 2 > \right)} \\ &+ 2^{\tau \left( < 1, 4, 2, 3 > \right)} \\ &+ 2^{\tau \left( < 1, 4, 3, 2 > \right)} \\ &+ 2^{\tau \left( < 1, 2, 3, 4 > \right)} \\ &+ \cdots \end{aligned}$ 这时我们发现, 将 $n = 4$ 的所有序列按照字典序排序后, 将前 $\left(n - 1\right)!$ 种排列的后三位离散化, 就是 $n = 3$ 时的所有情况情况. 假设我们已经知道了 $n = 3$ 时的答案, 且知道新增加的数是如何影响逆序对个数的, 我们就可以用递推解出此题.

显然的, 在一个序列前添加一个数, 增加的逆序对的数量是其后方比其小的数的个数. 具体地, 在上面的例子中, 当这个数是 $1$ 的时候, 增加的数量为 $0$ ; 当这个数是 $2$ 时, 增加的数量为零; 当这个数是 $\forall m \in \mathbb{N}, m \le n$ 时, 增加是数是 $n - 1$ .

设 $\sigma$ 为任意一个长度为 $n - 1$ 的排列, $\delta$ 为任意一个长度为 $n$ 的排列, 则:

$\begin{aligned} & \sum_{\delta}{2 ^ {\tau \left( \delta \right)}} \\ =& \sum_{i = 0}^{n - 1}{2^{i} \cdot \sum_{\sigma} {2^{\tau\left(\sigma\right)}}} \\ =& \sum_{\sigma} {2^{\tau\left( \sigma \right)}} \cdot \sum_{i = 0} ^ {n - 1} {2 ^ {i}} \\ =& \left( 2 ^ {n} - 1 \right) \cdot \sum_{\sigma} {2^{\tau\left( \sigma \right)}} \end{aligned}$

定义 $f\left( x \right)$ 是 $n = x$ 时的答案, 则我们知道: $\begin{aligned} f \left( x \right) = f\left( x - 1 \right) \cdot ( 2 ^ i - 1) mod MOD \end{aligned}$ 其中 $MOD$ 是题目给定的模数. 我们只需要提前处理出 $2$ 的次幂, 就可以快速的得出答案.

代码

#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;
}

Table of contents

题目

分析

代码