CP-templates

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Misuki743/CP-templates

:heavy_check_mark: combi/bernoulliNumber.cpp

Verified with

Code

//#include<modint/MontgomeryModInt.cpp>
//#include<poly/NTTmint.cpp>
//#include<poly/FPS.cpp>

template<class Mint>
FPS<Mint> bernoulliNumber(int n) {
  fps fac(n + 2);
  fac[0] = 1;
  for(int i = 1; i <= n + 1; i++)
    fac[i] = fac[i - 1] * i;
  fps f(n + 2);
  f[n + 1] = Mint(1) / fac[n + 1];
  for(int i = n; i > 0; i--)
    f[i] = f[i + 1] * (i + 1);
  f.erase(f.begin());
  f = f.inv(n + 1);
  for(int i = 0; i <= n; i++)
    f[i] *= fac[i];
  return f;
}
#line 1 "combi/bernoulliNumber.cpp"
//#include<modint/MontgomeryModInt.cpp>
//#include<poly/NTTmint.cpp>
//#include<poly/FPS.cpp>

template<class Mint>
FPS<Mint> bernoulliNumber(int n) {
  fps fac(n + 2);
  fac[0] = 1;
  for(int i = 1; i <= n + 1; i++)
    fac[i] = fac[i - 1] * i;
  fps f(n + 2);
  f[n + 1] = Mint(1) / fac[n + 1];
  for(int i = n; i > 0; i--)
    f[i] = f[i + 1] * (i + 1);
  f.erase(f.begin());
  f = f.inv(n + 1);
  for(int i = 0; i <= n; i++)
    f[i] *= fac[i];
  return f;
}
Back to top page