結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー anta
提出日時 2018-03-09 22:52:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,046 bytes
コンパイル時間 1,746 ms
コンパイル使用メモリ 172,504 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-10 07:08:58
合計ジャッジ時間 2,475 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

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

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

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

	ModInt inverse() const {
		long long a = x, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		return ModInt(u);
	}
};
typedef ModInt<1000000007> mint;

template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
	ModInt<MOD> r = 1;
	while (k) {
		if (k & 1) r *= a;
		a *= a;
		k >>= 1;
	}
	return r;
}


void calculateInverses(vector<mint> &xs) {
	int n = (int)xs.size();
	vector<mint> prod(n + 1);
	prod[0] = 1;
	rep(i, n)
		prod[i + 1] = prod[i] * xs[i];
	mint invprod = prod[n].inverse();
	for (int i = n - 1; i >= 0; -- i) {
		mint x = xs[i];
		xs[i] = invprod * prod[i];
		invprod *= x;
	}
}

mint solve(const vector<mint> &A, mint T) {
	int N = (int)A.size() - 1;
	if (T.get() <= N)
		return A[T.get()];
	mint numprod = 1;
	rer(j, 0, N)
		numprod *= T - j;
	vector<mint> fact(N + 1);
	fact[0] = 1;
	rer(i, 1, N) fact[i] = fact[i - 1] * i;
	vector<mint> numinvs(N + 1);
	rer(i, 0, N)
		numinvs[i] = T - i;
	calculateInverses(numinvs);
	vector<mint> deninvs(N + 1);
	rer(i, 0, N)
		deninvs[i] = fact[i] * (fact[N - i] * ((N - i) % 2 == 0 ? 1 : -1));
	calculateInverses(deninvs);
	mint ans;
	rer(i, 0, N) {
		mint num = numprod * numinvs[i];
		ans += A[i] * num * deninvs[i];
	}
	return ans;
}

int main() {
	long long N; int K;
	while (~scanf("%lld%d", &N, &K)) {
		vector<mint> A(K + 2);
		reu(n, 1, A.size())
			A[n] = A[n - 1] + (mint(n) ^ K);
		mint ans = solve(A, N);
		printf("%d\n", ans.get());
	}
	return 0;
}
0