题目链接：LOJ 2058

在 2016 年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。

现在他想计算这样一个函数的值：

$$ f(n) = \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {i} S(i, j) \cdot 2 ^ {j} \cdot j! $$

$S(i, j)$ 表示第二类斯特林数，递推公式为: $S(i, j) = j \cdot S(i − 1, j) + S(i − 1, j − 1), 1 \le j \le i − 1$。

边界条件为：$S(i, i) = 1(i \ge 0), S(i, 0) = 0(i \ge 1)$。

你能帮帮她吗？

数据范围：$1 \le n \le 10 ^ {5}$。

Solution

我们直接写出第二类斯特林数的通项公式：

$$ S(n, m) = \frac{1}{m!} \sum_{i = 0} ^ {m} (-1) ^ {i} \binom{m}{i} (m - i) ^ {n} $$

代入得到：

$$ \begin{align*} f(n) & = \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {i} 2 ^ {j} \sum_{k = 0} ^ {j} (-1) ^ {k} \binom{j}{k} (j - k) ^ {i} \\ & = \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {i} 2 ^ {j} \sum_{k = 0} ^ {j} (-1) ^ {k} \frac{j!}{k! \cdot (j - k)!} (j - k) ^ {i} \\ & = \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {i} 2 ^ {j} \cdot j! \sum_{k = 0} ^ {j} \frac{(-1) ^ {k}}{k!} \frac{(j - k) ^ {i}}{(j - k)!} \\ & = \sum_{j = 0} ^ {n} 2 ^ {j} \cdot j! \sum_{k = 0} ^ {j} \frac{(-1) ^ {k}}{k!} \frac{\sum_{i = 0} ^ {n} (j - k) ^ {i}}{(j - k)!} \\ \end{align*} $$

设 $g(i) = \frac{(-1) ^ {i}}{i!}, h(i) = \frac{\sum_{j = 0} ^ n i ^ {j}}{i!} = \frac{i ^ {n +1} - 1}{(i - 1) \cdot i!}$。特殊地 $h(0) = 1, h(1) = n + 1$，那么答案为：

$$ \sum_{i = 0} ^ {n} 2 ^ {i} \cdot i! (g \ast h)(i) $$

直接做一遍卷积即可。

时间复杂度：$\mathcal O(n \log n)$。

Code

/* 此处省略多项式模板 */

const int N = 1e5;

int n, fac[N + 5], ifac[N + 5], pw[N + 5], in[N + 5];
std::vector<int> prime;
bool flg[N + 5];

void sieve(int n, int k) {
    std::fill(flg + 2, flg + n + 1, true);
    for (int i = 2; i <= n; i++) {
        if (flg[i]) prime.push_back(i), pw[i] = pow(i, k);
        for (auto j : prime) {
            if (i * j > n) break;
            flg[i * j] = false;
            pw[i * j] = 1LL * pw[i] * pw[j] % MOD;
            if (i % j == 0) continue;
        }
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    ifac[n] = inv(fac[n]);
    for (int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
    in[1] = 1;
    for (int i = 2; i <= n; i++) {
        in[i] = 1LL * (MOD - MOD / i) * in[MOD % i] % MOD;
    }
}
int main() {
    int n;
    scanf("%d", &n);
    sieve(n, n + 1);
    Vec F(n + 1), G(n + 1);
    for (int i = 0, sgn = 1; i <= n; i++, sgn = MOD - sgn) {
        F[i] = 1LL * sgn * ifac[i] % MOD;
    }
    G[0] = 1, G[1] = n + 1;
    for (int i = 2; i <= n; i++) {
        G[i] = 1LL * (pw[i] - 1) * in[i - 1] % MOD * ifac[i] % MOD;
    }
    F = F * G;
    int ans = 0;
    for (int p2 = 1, i = 0; i <= n; p2 = 2LL * p2 % MOD, i++) {
        add(ans, 1LL * p2 * fac[i] % MOD * F[i] % MOD);
    }
    printf("%d\n", ans);
    return 0;
}