求\(\sum_{i = 0}^n\sum_{j = 0}^i \begin{Bmatrix}i\\ j\end{Bmatrix}2^jj!\)。

\(1\leq n\leq 10^5\)。

一直没做qwq……

推推柿子：

\[
\begin{aligned}
\quad&\sum_{i = 0}^n\sum_{j = 0}^i \begin{Bmatrix}i\\ j\end{Bmatrix}2^jj!\\
=&\sum_{j = 0}^n 2^j\sum_{i = 0}^n\begin{Bmatrix}i\\ j\end{Bmatrix}j!\\
=&\sum_{j = 0}^n 2^j\sum_{i = 0}^n\sum_{k = 0}^j (-1)^{j - k}\binom{j}{k}k^i\\
=&\sum_{j = 0}^n 2^j j!\sum_{k = 0}^j \frac{(-1)^{j - k}}{(j - k)!}\frac{\sum_{i = 0}^n k^i}{k!}
\end{aligned}
\]

观察后面的和式，是一个卷积的形式，然后随便做了……

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <utility>
typedef long long ll;
const ll ha = 998244353LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

const int maxn = 400005;
ll fac[maxn], ifac[maxn];
void process() {
  fac[0] = 1;
  for(int i = 1; i < maxn; i ++) {
    fac[i] = fac[i - 1] * (ll)i % ha;
  }
  ifac[maxn - 1] = inv(fac[maxn - 1]);
  for(int i = maxn - 2; i >= 0; i --) {
    ifac[i] = ifac[i + 1] * (ll(i + 1)) % ha;
  }
}

int flip(int bi, int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans |= (1 << (bi - i - 1));
    }
  }
  return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int v = flip(bi, i);
    if(v < i) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    ll xi_n = pow_mod(3, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi_n = inv(xi_n);
    for(int i = 0; i < n; i += (L << 1)) {
      ll xi = 1;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        ll bp = xi * y % ha;
        A[j] = (x + bp) % ha;
        A[j + L] = (x - bp + ha) % ha;
        xi = xi * xi_n % ha;
      }
    }
  }
  if(flag) {
    ll inv_n = inv(n);
    for(int i = 0; i < n; i ++) {
      A[i] = A[i] * inv_n % ha;
    }
  }
}

ll A[maxn], B[maxn];
int main() {
  process();
  int n; scanf("%d", &n);
  A[0] = 1; A[1] = n + 1;
  for(int i = 2; i <= n; i ++) {
    A[i] = pow_mod(i, n + 1) - 1LL;
    A[i] = A[i] * inv(i - 1) % ha;
    A[i] = A[i] * ifac[i] % ha;
  }
  for(int i = 0; i <= n; i ++) {
    B[i] = ifac[i];
    if(i & 1) B[i] = ha - B[i];
  }
  int bi = 0, len = 1;
  while(len <= (n << 1)) {
    len <<= 1; bi ++;
  }
  NTT(A, bi); NTT(B, bi);
  for(int i = 0; i < len; i ++) {
    A[i] = A[i] * B[i] % ha;
  }
  NTT(A, bi, true);
  ll pw = 1LL;
  ll ans = 0;
  for(int i = 0; i <= n; i ++) {
    ll p = pw * fac[i] % ha;
    ans = (ans + p * A[i]) % ha;
    pw = pw * 2LL % ha;
  }
  printf("%lld\n", ans);
  return 0;
}

• 相关文章
• 全局相关文章