#246736 (C++17) No.665 Bernoulli Bernoulli

• 問題: No.665 Bernoulli Bernoulli
• ユーザー: kazuma
• 提出日時: 2018-03-24 06:12:28
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 18 ms / 2,000 ms
• コード長: 2,088 bytes
• コンパイル時間: 2,184 ms
• コンパイル使用メモリ: 202,568 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-07 08:21:21
• 合計ジャッジ時間: 3,333 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	9 ms; 4,376 KB
testcase_03	AC	16 ms; 4,380 KB
testcase_04	AC	15 ms; 4,376 KB
testcase_05	AC	15 ms; 4,376 KB
testcase_06	AC	16 ms; 4,380 KB
testcase_07	AC	15 ms; 4,380 KB
testcase_08	AC	15 ms; 4,376 KB
testcase_09	AC	16 ms; 4,376 KB
testcase_10	AC	15 ms; 4,380 KB
testcase_11	AC	17 ms; 4,380 KB
testcase_12	AC	17 ms; 4,380 KB
testcase_13	AC	18 ms; 4,380 KB
testcase_14	AC	16 ms; 4,380 KB
testcase_15	AC	15 ms; 4,380 KB
testcase_16	AC	15 ms; 4,376 KB
testcase_17	AC	16 ms; 4,376 KB
testcase_18	AC	15 ms; 4,380 KB

ソースコード

#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, int n) {
	int k = ys.size() - 1;
	if (n <= k) return ys[n];
	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 * (qt / n);
	for (int i = 1; i <= k; i++) {
		qi = (qi * i) / (MD - k + (i - 1));
		res += ys[i] / qi * (qt / (n - i));
	}
	return res;
}

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, mod - 1) * mint(n / mod) + lagrange_polynomial(ys, n % mod)).get() << endl;
	return 0;
}