yukicoder No.329 全射 - mayoko’s diary

問題

解法

集合 $A_i$ から集合 $A_j$ への生きている全射がある条件は, あるパス $i \rightarrow ... \rightarrow j$ が存在して, そのパスに含まれる数 a がすべて $|A_a| >= |A_j|$ を満たすことです。

これは, 要するにパスに含まれる数字について, $A_a$ の最小値 (これを $D_{ij}$ とする) が $|A_j|$ 以上であるということで,
d[i][j] = (i から j までのパスのうち, $D_{ij}$ が最大となるパスにおける $D_{ij}$ ) とおけば, d[i][j] >= $|A_j|$ のとき生きている全射が存在するわけです。ということで, d[i][j] を求めたいですが, これは warshall-floyd と同じアルゴリズムで求めることが出来ます。

i から j へ生きている全射があるとわかったら, 全射であるような関数がいくつあるのかを求めたいです。
w[i] 個の要素がある集合から w[j] 個の要素がある集合への写像の個数は, w[j]^w[i] 個あります。ただ, これだと全射になっていないことがあるので, 引いたり足したりする例のアレをやります。calc 関数でやってるのでそれを参考に。

const int MAXN = 222;
const int MAX = 1011;
const ll MOD = 1e9+7;
int w[MAXN];
int d[MAXN][MAXN];
ll nCr[MAX][MAX];
ll pm[MAX][MAX];

ll pow_mod(ll x, int p) {
    if (x == 0) return 0;
    if (p == 0) return 1;
    if (p == 1) return x;
    if (p%2) return (x*pow_mod(x, p-1))%MOD;
    ll tmp = pow_mod(x, p/2);
    return (tmp*tmp)%MOD;
}

ll calc(int from, int to) {
    ll ret = 0;
    for (int i = 1; i <= to; i++) {
        ll tmp = nCr[to][i] * pm[i][from] % MOD;
        if ((to-i)%2) tmp *= -1;
        ret += tmp;
    }
    ret %= MOD;
    if (ret < 0) ret += MOD;
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < MAX; i++) {
        nCr[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            nCr[i][j] = nCr[i-1][j-1] + nCr[i-1][j];
            nCr[i][j] %= MOD;
        }
    }
    for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) {
        pm[i][j] = pow_mod(i, j);
    }
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> w[i];
    for (int i = 0; i < N; i++) d[i][i] = w[i];
    for (int i = 0; i < M; i++) {
        int from, to;
        cin >> from >> to;
        from--; to--;
        d[from][to] = min(w[from], w[to]);
    }
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (w[j] <= d[i][j]) ans += calc(w[i], w[j]);
    }
    ans %= MOD;
    cout << ans << endl;
    return 0;
}