結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー snrnsidy
提出日時 2021-10-22 20:19:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 858 bytes
コンパイル時間 588 ms
コンパイル使用メモリ 40,704 KB
最終ジャッジ日時 2025-01-25 02:59:52
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1 RE * 1
other RE * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
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) {
      |              ^~~~
main.cpp: In function ‘int read(int)’:
main.cpp:5:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    5 | int read(int x = 0) { return scanf("%d", &x), x; }
      |                              ~~~~~^~~~~~~~~~

ソースコード

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