TJOI2016 求和

$$ \text{题意:} \\ \text{求}f\left( n \right) =\sum_{0\le i\le n}{\sum_{0\le j\le i}{S_2\left( i,j \right) \times 2^j\times j!}} \\ \text{第二类斯特林数的通项公式:} \\ S\left( i,j \right) =\frac{1}{j!}\sum_{0\le k\le j}{\left( \begin{array}{c} j\\ k\\ \end{array} \right) \left( -1 \right) ^{j-k}k^i} \\ \text{代入,因为}j>i\text{时,}S_2\left( i,j \right) \text{为0，所以求和上界可以放到}n \\ f\left( n \right) =\sum_{0\le j\le n}{2^j\times j!\sum_{0\le i\le n}{S\left( i,j \right)}} \\ f\left( n \right) =\sum_{0\le j\le n}{2^j\sum_{0\le i\le n}{\sum_{0\le k\le j}{\left( \begin{array}{c} j\\ k\\ \end{array} \right) \times \left( -1 \right) ^{j-k}k^i}}} \\ \text{整理一下} \\ f\left( n \right) =\sum_{0\le j\le n}{j!\sum_{0\le k\le j}{\frac{2^j}{k!\left( j-k \right) !}\times \left( -1 \right) ^{j-k}}\sum_{0\le i\le n}{k^i}} \\ \text{注意，}\sum_{0\le i\le n}{k^i}\text{可以直接用等比数列求和公式}O\left( 1 \right) \text{计算！} \\ =\sum_{0\le j\le n}{j!\times 2^j\sum_{0\le k\le j}{\frac{\sum_{0\le i\le n}{k^i}}{k!}\times \frac{\left( -1 \right) ^{j-k}}{\left( j-k \right) !}}} \\ \text{这个式子可以卷积} \\ f\left( n \right) =\sum_{0\le j\le n}{j!\sum_{0\le k\le j}{\frac{\left( -1 \right) ^k\sum_{0\le i\le n}{k^i}}{k!}\times \frac{1}{\left( j-k \right) !}}} \\ \\ $$

#include <iostream>
#include <algorithm>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;

using int_t = long long int;

const int_t mod = 998244353;
const int_t g = 3;
const int_t LARGE = 1 << 20;

int_t power(int_t base, int_t index);
int_t bitRev(int_t x, int_t size2);
template <int_t arg = 1>
void transform(int_t *A, int_t size);
int_t upper2n(int_t x);

int_t sum(int_t k, int_t n)
{
    if (k == 1)
        return (n + 1) % mod;
    // if(k==0) return 0;s
    return ((power(k, n + 1) - 1) % mod * power(k - 1, -1) % mod) % mod;
}

int main()
{
    int_t n;
    cin >> n;
    static int_t fact[LARGE] = {1};
    for (int_t i = 1; i <= n * 2; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    static int_t A[LARGE];
    static int_t B[LARGE];
    int_t size = upper2n(2 * n + 1);
    for (int_t i = 0; i <= n; i++)
    {
        A[i] = ((sum(i, n)) % mod * power(fact[i], -1) % mod + mod) % mod;
        B[i] = power(fact[i], -1) * power(-1, i) % mod;
        // cout<<A[i]<<" ";
    }
    transform(A, size);
    transform(B, size);
    for (int_t i = 0; i <= size; i++)
        A[i] = A[i] * B[i] % mod;
    transform<-1>(A, size);
    int_t result = 0;
    for (int_t i = 0; i <= n; i++)
    {
        A[i] = A[i] * power(size, -1) % mod * fact[i] % mod * power(2, i) % mod;
        result = (result + A[i]) % mod;
    }
    cout << result << endl;
    return 0;
}

template <int_t arg = 1>
void transform(int_t *A, int_t size)
{
    int_t size2 = log2(size);
    for (int_t i = 0; i < size; i++)
    {
        int_t x = bitRev(i, size2);
        if (x > i)
            std::swap(A[i], A[x]);
    }
    for (int_t i = 2; i <= size; i *= 2)
    {
        int_t mr = power(g, arg * (mod - 1) / i);
        for (int_t j = 0; j < size; j += i)
        {
            int_t curr = 1;
            for (int_t k = 0; k < i / 2; k++)
            {
                int_t u = A[j + k];
                int_t t = A[j + k + i / 2] * curr % mod;
                A[j + k] = (u + t) % mod;
                A[j + k + i / 2] = (u - t + mod) % mod;
                curr = (curr * mr) % mod;
            }
        }
    }
}

int_t upper2n(int_t x)
{
    int_t result = 1;
    while (result < x)
        result *= 2;
    return result;
}

int_t bitRev(int_t x, int_t size2)
{
    int_t result = 0;
    for (int_t i = 1; i < size2; i++)
    {
        result |= (x & 1);
        x >>= 1;
        result <<= 1;
    }
    return result | (x & 1);
}
int_t power(int_t base, int_t index)
{
    base = (base % mod + mod) % mod;
    if (index < 0)
    {
        index *= -1;
        base = power(base, mod - 2);
    }
    int_t result = 1;
    while (index)
    {
        if (index & 1)
        {
            result = result * base % mod;
        }
        base = base * base % mod;
        index >>= 1;
    }
    return result;
}