raw source code
#include<bits/stdc++.h>

using namespace std;

struct Combination {
  int mod;
  vector< int64_t > mfact, rmfact;

  Combination(int sz, int mod) : mfact(sz + 1), rmfact(sz + 1), mod(mod) {
    mfact[0] = 1;
    for(int i = 1; i < mfact.size(); i++) {
      mfact[i] = mfact[i - 1] * i % mod;
    }
    rmfact[sz] = inv(mfact[sz]);
    for(int i = sz - 1; i >= 0; i--) {
      rmfact[i] = rmfact[i + 1] * (i + 1) % mod;
    }
  }

  int64_t fact(int k) const {
    return (mfact[k]);
  }

  int64_t rfact(int k) const {
    return (rmfact[k]);
  }

  int64_t pow(int64_t x, int64_t n) const {
    int64_t ret = 1;
    while(n > 0) {
      if(n & 1) (ret *= x) %= mod;
      (x *= x) %= mod;
      n >>= 1;
    }
    return (ret);
  }

  int64_t inv(int64_t x) const {
    return (pow(x, mod - 2));
  }

  int64_t P(int n, int r) const {
    if(r < 0 || n < r) return (0);
    return (mfact[n] * rmfact[n - r] % mod);
  }

  int64_t C(int p, int q) const {
    if(q < 0 || p < q) return (0);
    return (mfact[p] * rmfact[q] % mod * rmfact[p - q] % mod);
  }

  int64_t H(int n, int r) const {
    if(n < 0 || r < 0) return (0);
    return (r == 0 ? 1 : C(n + r - 1, r));
  }
};


int64_t bell_number(int n, int mod) {
  Combination table(n + 1, mod);
  vector< int64_t > subfactorial(n + 1);
  subfactorial[0] = 1;
  for(int i = 2; i <= n; i++) {
    subfactorial[i] = (subfactorial[i - 1] + subfactorial[i - 2]) * (i - 1);
    subfactorial[i] %= mod;
  }
  int64_t ret = 0;
  for(int m = 0; m <= n; m++) {
    int64_t add = table.pow(m, n) * subfactorial[n - m] % mod;
    (add *= table.rfact(m)) %= mod;
    (add *= table.rfact(n - m)) %= mod;
    (ret += add) %= mod;
  }
  return ret;
}

const int mod = 1e9 + 7;

int main() {
  int N;
  cin >> N;
  cout << bell_number(N, mod) << endl;
}
# ユーザ名 問題 言語 状態 得点 提出日時
00284 ei13333 0014 - ベル数 C++11 AC 100 18-04-25 22:29

セット

# セット 得点 Cases
1 ALL 50 / 50 *
2 partial 50 / 50 test-partial-*.txt

テストケース

テストケース取得

ファイル名 状態 実行時間 メモリ使用量 #
test-full-11.txt AC 70 ms 3680 KB 1
test-full-12.txt AC 70 ms 3680 KB 1
test-full-13.txt AC 70 ms 3420 KB 1
test-full-14.txt AC 50 ms 2892 KB 1
test-full-15.txt AC 70 ms 3684 KB 1
test-partial-1.txt AC 20 ms 1524 KB 1 2
test-partial-10.txt AC 70 ms 1520 KB 1 2
test-partial-2.txt AC 20 ms 1520 KB 1 2
test-partial-3.txt AC 20 ms 1524 KB 1 2
test-partial-4.txt AC 20 ms 1520 KB 1 2
test-partial-5.txt AC 20 ms 1524 KB 1 2
test-partial-6.txt AC 20 ms 1520 KB 1 2
test-partial-7.txt AC 20 ms 1520 KB 1 2
test-partial-8.txt AC 30 ms 1520 KB 1 2
test-partial-9.txt AC 30 ms 1520 KB 1 2