自动搬运

查看原文

来自洛谷，原作者为

	Rainybunny / 我是否能成为谁 关于大海的形容 /

搬运于2025-08-24 22:39:23，当前版本为作者最后更新于2022-02-12 21:27:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathscr{Description}$

  Link. (It's empty temporarily.)

  给定 $n$，设 $\sigma$ 为长度为 $n$ 的排列，求

  $n\le10^7$。

$\mathscr{Solution}$

  简化一个巨难的 idea，得到了 T1 qwq。

$\mathscr{Subtasks}$

  Subtask 1 考察选手动手能力，并借此鼓励选手 OEIS。（

  Subtask 2 考察 std::next_permutation 的使用，并借此让选手笃定 OEIS 结果。（

  Subtask 3 献给 $\mathcal O(n^4)\sim\mathcal O(n^3)$ 的解法，暂时没想到合情合理的暴力。

  Subtask 4 献给朴素的 $\mathcal O(n^2)$ DP。

  Subtask 5 献给正解，献给所有参赛选手。

$\mathscr{Body}$

  其实它是 A005329，但因为是 T1 所以就不要在意细节了 awa。

  考虑 DP，令 $f(i)$ 表示 $n=i$ 时的答案。对于转移，发现 $\sigma[2:]$（下标从 $1$ 开始，这里指从 $\sigma_2$ 开始的后缀） 对应了 $n-1$ 的子问题。也就是说，若 $\sigma_1$ 固定，所有 $\sigma[2:]$ 的答案之和为 $f(i-1)$，与 $\sigma$ 具体取值无关。接着，枚举 $\sigma_1$ 的值，与 $\sigma_1$ 构成的逆序对数可以轻易算出，因此得到转移：

进一步，从 $\mathcal O(n^2)$ 到 $\mathcal O(n)$ 仅需将和式化为等比数列求和，有：

于是，答案 $f(n)$ 即是

  如果有花里胡哨爱好者, 可以快速 $q-$ 阶乘求 $[n]_q!$ 在 $q=2$ 处的值, $\mathcal O(\sqrt n\log n)$.

$\mathscr{Code}$

/*+Rainybunny+*/

#include <bits/stdc++.h>

const int MOD = 1e9 + 7;

int main() {
    int n, ans = 1, pwr = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        (pwr <<= 1) >= MOD && (pwr -= MOD);
        ans = ans * (pwr - 1ll) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}