結果

問題 No.140 みんなで旅行
コンテスト
ユーザー kimiyuki
提出日時 2016-02-24 01:45:48
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 14 ms / 5,000 ms
コード長 1,842 bytes
コンパイル時間 625 ms
コンパイル使用メモリ 67,584 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 13:15:32
合計ジャッジ時間 1,474 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;

ll powi(ll x, ll y, ll p) {
    x = (x % p + p) % p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) {
    assert ((x % p + p) % p != 0);
    return powi(x, p-2, p);
}
const ll mod = 1e9+7;
ll choose(ll n, ll r) { // O(n), O(1)
    static vector<ll> fact(1,1);
    static vector<ll> ifact(1,1);
    if (fact.size() <= n) {
        int l = fact.size();
        fact.resize( n + 1);
        ifact.resize(n + 1);
        repeat_from (i,l,n+1) {
            fact[i]  = fact[i-1] * i % mod;
            ifact[i] = inv(fact[i], mod);
        }
    }
    r = min(r, n - r);
    return fact[n] * ifact[n-r] % mod * ifact[r] % mod;
}
ll second_kind_stirling(ll n, ll k) { // O(nk)
    assert (0 <= n and 0 <= k);
    if (n  < k) return 0;
    if (n == k) return 1;
    if (k == 0) return 0;
    static vector<vector<ll> > memo;
    if (memo.size() <= n) {
        int l = memo.size();
        memo.resize(n + 1);
        repeat_from (i,l,n+1) memo[i].resize(i);
    }
    if (memo[n][k]) return memo[n][k];
    return memo[n][k] = (second_kind_stirling(n-1, k-1) + k * second_kind_stirling(n-1, k) % mod) % mod;
}

int main() {
    int n; cin >> n;
    ll ans = 0;
    repeat_from (a,1,n+1) { // a is # pairs which they both are in the same group
        int b = n - a; // b is # not
        repeat_from (k,1,a+1) {
            ll cnt = choose(n,a) * second_kind_stirling(a,k) % mod * powi(k * (k-1), b, mod) % mod;
            ans = (ans + cnt) % mod;
        }
    }
    cout << ans << endl;
    return 0;
}
0