練習会で。 後輩が考察して「初めて動的計画法書いた」とか言いながら通した。 私はさっぱり分からなかった。

同じグループに入る夫婦の数を固定、というのが鍵だったようだが、これはどうやって思い付けばよかったのだろう。 数える対象の全体を数え易いように分割したい、という向きから入って、何か分割できそうな要素を探せばよかったのだろうか。 クエリっぽいDPで押し通す方法もあるっぽいけど。

No.140 みんなで旅行

解法

同じグループに入る夫婦の数を固定し、グループの数を固定する。$O(N^2)$。

$A$組の夫婦が同じグループに入り、$K$個のグループがあるとする。 この条件を満たす組合せの数は${}_NC_A \cdot S_{A,K} \cdot \{ K(K-1) \}^B$である。 ただし濃度$N$の有限集合の部分集合で濃度$K$のものの数(第2種stirling数)を$S_{N,K}$とする。

実装

ライブラリで、今まで別個に実装がなされていたpowiとinvをまとめた。

#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;
}