結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー snrnsidy
提出日時 2021-10-22 20:19:42
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 858 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 282 ms
コンパイル使用メモリ 57,696 KB
実行使用メモリ 7,968 KB
最終ジャッジ日時 2026-06-23 10:24:39
合計ジャッジ時間 2,605 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 2
other RE * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:27:14: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' [-Wc++20-extensions]
   27 | int f(int k, auto& d) {
      |              ^~~~

ソースコード

diff #
raw source code 

#include<cstdio>
#include<array>
using namespace std;
constexpr int MOD = 1e9 + 7;
int read(int x = 0) { return scanf("%d", &x), x; }

int pow(int n, int k, int ret = 1) {
	for (int mul = n; k; k >>= 1) {
		if (k & 1) ret = ret *1L* mul % MOD;
		mul = mul *1L* mul % MOD;
	}
	return ret;
}

auto&& binomial = [](){
	array<array<int, 52>, 52> d {{1}};
	for (int i = 1; i <= 51; i++) {
		d[i][0] = 1;
		for (int j = 1; j <= i; j++)
			d[i][j] = (d[i-1][j] + d[i-1][j-1]) % MOD;
	}
	return d;
}();

int n = read();

int f(int k, auto& d) {
	if (k == 0) return n;
	if (d[k]) return d[k];

	int ans = (pow(n+1, ++k) - 1 + MOD) % MOD;
	for (int i = 2; i <= k; i++) {
		ans = ((ans - binomial[k][i] *1L* f(k-i, d) % MOD) % MOD + MOD) % MOD;
	}

	return d[k-1] = ans *1L* pow(k, MOD-2) % MOD;
}

int main() {
	int d[52] {};
	return printf("%d\n", f(read(), d)), 0;
}
0