結果

問題 No.665 Bernoulli Bernoulli
ユーザー snrnsidysnrnsidy
提出日時 2021-10-22 20:19:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 858 bytes
コンパイル時間 456 ms
コンパイル使用メモリ 48,896 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 02:21:40
合計ジャッジ時間 3,490 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:27:14: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   27 | int f(int k, auto& d) {
      |              ^~~~

ソースコード

diff # 

#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