結果

問題 No.665 Bernoulli Bernoulli
ユーザー kazumakazuma
提出日時 2018-03-24 06:52:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 2,033 bytes
コンパイル時間 2,181 ms
コンパイル使用メモリ 203,500 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-25 02:42:20
合計ジャッジ時間 3,030 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 7 ms
5,376 KB
testcase_04 AC 7 ms
5,376 KB
testcase_05 AC 8 ms
5,376 KB
testcase_06 AC 7 ms
5,376 KB
testcase_07 AC 7 ms
5,376 KB
testcase_08 AC 7 ms
5,376 KB
testcase_09 AC 7 ms
5,376 KB
testcase_10 AC 7 ms
5,376 KB
testcase_11 AC 8 ms
5,376 KB
testcase_12 AC 7 ms
5,376 KB
testcase_13 AC 8 ms
5,376 KB
testcase_14 AC 8 ms
5,376 KB
testcase_15 AC 7 ms
5,376 KB
testcase_16 AC 8 ms
5,376 KB
testcase_17 AC 7 ms
5,376 KB
testcase_18 AC 7 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<int MOD>
struct mod_int {
	static const int Mod = MOD;
	unsigned x;
	mod_int() : x(0) { }
	mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	mod_int &operator/=(mod_int that) { return *this *= that.inverse(); }

	mod_int operator+(mod_int that) const { return mod_int(*this) += that; }
	mod_int operator-(mod_int that) const { return mod_int(*this) -= that; }
	mod_int operator*(mod_int that) const { return mod_int(*this) *= that; }
	mod_int operator/(mod_int that) const { return mod_int(*this) /= that; }

	mod_int inverse() const {
		long long a = x, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		return mod_int(u);
	}
};

template <int MD>
mod_int<MD> lagrange_polynomial(const vector<mod_int<MD>>& ys, long long n) {
	int k = ys.size() - 1;
	if (n <= k) return ys[n];
	n %= MD;
	mod_int<MD> qi = 1, qt = n;
	for (int i = 1; i <= k; i++) {
		qi *= MD - i;
		qt *= n - i;
	}
	mod_int<MD> res = ys[0] / (qi * n);
	for (int i = 1; i <= k; i++) {
		(qi *= i) /= MD - k + (i - 1);
		res += ys[i] / (qi * (n - i));
	}
	return res * qt;
}

const int mod = 1e9 + 7;

using mint = mod_int<mod>;

template <typename T>
T power(T x, int n) {
	T res = 1;
	while (n) {
		if (n & 1) {
			res *= x;
		}
		x *= x;
		n >>= 1;
	}
	return res;
}

int main()
{
	ll n;
	int k;
	cin >> n >> k;
	vector<mint> ys(k + 2);
	for (int i = 1; i <= k + 1; i++) {
		ys[i] = ys[i - 1] + power(mint(i), k);
	}
	cout << lagrange_polynomial(ys, n).get() << endl;
	return 0;
}
0