結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー kazuma
提出日時 2018-03-24 06:12:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,088 bytes
コンパイル時間 2,008 ms
コンパイル使用メモリ 197,012 KB
最終ジャッジ日時 2025-01-05 09:33:19
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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, 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;
}
0