#697011 (C++14) No.140 みんなで旅行

• 問題: No.140 みんなで旅行
• ユーザー: atjh16
• 提出日時: 2021-09-07 19:14:16
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 12 ms / 5,000 ms
• コード長: 845 bytes
• コンパイル時間: 1,509 ms
• コンパイル使用メモリ: 165,984 KB
• 実行使用メモリ: 8,280 KB
• 最終ジャッジ日時: 2023-08-25 11:12:28
• 合計ジャッジ時間: 3,078 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,404 KB
testcase_01	AC	2 ms; 5,388 KB
testcase_02	AC	3 ms; 5,996 KB
testcase_03	AC	2 ms; 5,380 KB
testcase_04	AC	2 ms; 5,504 KB
testcase_05	AC	2 ms; 5,420 KB
testcase_06	AC	2 ms; 5,500 KB
testcase_07	AC	2 ms; 5,720 KB
testcase_08	AC	2 ms; 5,524 KB
testcase_09	AC	2 ms; 5,444 KB
testcase_10	AC	2 ms; 5,440 KB
testcase_11	AC	12 ms; 8,216 KB
testcase_12	AC	2 ms; 5,976 KB
testcase_13	AC	2 ms; 5,772 KB
testcase_14	AC	12 ms; 8,252 KB
testcase_15	AC	12 ms; 8,248 KB
testcase_16	AC	6 ms; 6,964 KB
testcase_17	AC	4 ms; 6,412 KB
testcase_18	AC	9 ms; 7,948 KB
testcase_19	AC	10 ms; 8,280 KB
testcase_20	AC	4 ms; 6,356 KB
testcase_21	AC	2 ms; 5,616 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

long long n, m = 1;
const long long M = 1e9 + 7;
long long p[556][556], c[556][556];

long long powm(long long a, long long b) {
	long long u = 1, v = a;

	while (b > 0) {
		if (b & 1)
			u = u * v % M;

		b >>= 1;
		v = v * v % M;
	}

	return u;
}

int main()
{
	cin >> n;

	c[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		c[i][0] = 1;
		c[i][i] = 1;

		for (int j = 1; j < n; j++)
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % M;
	}

	p[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		p[i][0] = 1;
		p[i][i] = 1;

		for (long long j = 1; j < n; j++)
			p[i][j] = (p[i - 1][j - 1] + (j + 1) * p[i - 1][j]) % M;
	}

	for (long long i = 1; i < n; i++) {
		for (long long j = 0; j < n - i; j++) {
			m = (m + p[n - j - 1][i] * c[n][j] % M * powm(i * (i + 1), j) % M) % M;
		}
	}

	cout << m << endl;
}