mayoko’s diary

プロコンとかいろいろ。

yukicoder No.329 全射

解法

集合  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;
}