結果

問題 No.140 みんなで旅行
ユーザー Tatamo
提出日時 2016-02-24 00:55:44
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 157 ms / 5,000 ms
コード長 1,850 bytes
コンパイル時間 543 ms
コンパイル使用メモリ 59,584 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-09-22 13:15:27
合計ジャッジ時間 2,306 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<algorithm>
#define MOD (1000000007)
using namespace std;
/*long long combination(int n, int r) {
    long long result = 1;
    for (int i = 1; i <= r; i++) {
        result *= (n - i + 1);
        result /= i;
    }
    return result;
}
long long stirling2(int n, int k) {
    long long result;
    if (k > n) throw;
    if (k == 0) return 0;
    if (k == 1 || k == n) return 1;
    return k*stirling2(n - 1, k) + stirling2(n - 1, k - 1);
}*/
long long **C;
long long **S;
void generateStirling2(int n) {
    for (int i = 0; i <= n; i++) {
        for (int ii = 0; ii <= i; ii++) {
            if (ii == 0) S[i][ii] = 0;
            else if (ii == 1 || ii == i) S[i][ii] = 1;
            else S[i][ii] = (ii*S[i - 1][ii] + S[i - 1][ii - 1]) % MOD;
            //cout << "S[" << i << "][" << ii << "]: " << S[i][ii] << "  ";
        }
        //cout << endl;
    }
}
void generateCombination(int n) {
    for (int i = 0; i <= n; i++) {
        for (int ii = 0; ii <= i; ii++) {
            if (ii == 0) C[i][ii] = 1;
            else if (ii == i) C[i][ii] = 1;
            else C[i][ii] = (C[i - 1][ii - 1] + C[i - 1][ii]) % MOD;
            //cout << "C[" << i << "][" << ii << "]: " << C[i][ii] << "  ";
        }
        //cout << endl;
    }
}
long long _pow(int x, int y) {
    long long result = 1;
    for (int i = 0; i < y; i++) {
        result *= x;
        result %= MOD;
    }
    return result;
}
// problems/251
int main() {
    int n;
    cin >> n;
    C = new long long*[n + 1];
    S = new long long*[n + 1];
    for (int i = 0; i <= n; i++) {
        C[i] = new long long[n + 1];
        S[i] = new long long[n + 1];
    }
    generateCombination(n);
    generateStirling2(n);
    long result = 1; // 1:グループが1通りの場合
    for (int r = 1; r <= n; r++) {
        for (int k = 2; k <= r; k++) { // グループが2通りの場合からはじめる
            long long cmb = C[n][r];
            result += ((cmb * S[r][k]) % MOD * _pow((k*(k - 1)), n - r)) % MOD;
            result %= MOD;
        }
    }
    cout << result << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0