[LibreOJ 2058][TJOI2016]求和

danihao123 posted @ 2018年9月27日 20:49 in 题解 with tags loj 第二类斯特林数 斯特林反演 NTT FFT TJOI , 1009 阅读
转载请注明出处:http://danihao123.is-programmer.com/

求\(\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;
}
Grammarly Alternativ 说:
Aug 08, 2022 07:31:21 PM

Well, to be precise it is very important for anything to run properly such as a business creative which is grammar perfect or else a news outlet or a blog article which is properly checked for any grammar mistakes. Grammarly Alternative At the same time, people love to believe that working knowledge of grammar better resides with humans but it is true that the modern softwares, tools and plugins like Grammarly has been a great help to anyone who is looking to ensure that their words make sense.

AP 10th Evs Model Pa 说:
Sep 19, 2022 12:46:28 AM

Advised to everyone can contact the class teacher to get important questions for all lessons and topics of EVS. Every Telugu Medium, English Medium and Urdu Medium student of the State Board can download the AP 10th Class EVS Model Paper 2023 Pdf with answers for term-1 & term-2 exams of SA-1, SA-2 and other exams of the board. AP 10th Evs Model Paper Environmental Education is one of the most important subjects and it’s a part of Science. School Education Department and various leading private school teaching staff have designed and suggested the practice question paper for all Part-A, Part-B, Part-C, and Part-D questions of SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 and Assignments.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter