Solution -「GLR-R3」A

· · 题解

\mathscr{Description}

  [Link](). (It's empty temporarily.)

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

\sum_{\sigma}2^{\tau(\sigma)}\bmod (10^9+7).

  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 构成的逆序对数可以轻易算出，因此得到转移：

f(i)=\sum_{\sigma_1=1}^i2^{\sigma_1-1}f(i-1).

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

f(i)=(2^i-1)f(i-1).

于是，答案 f(n) 即是

\prod_{i=1}^n(2^i-1).

  如果有花里胡哨爱好者, 可以快速 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;
}