結果
問題 |
No.329 全射
|
ユーザー |
|
提出日時 | 2016-12-27 15:35:00 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 302 ms / 2,000 ms |
コード長 | 1,944 bytes |
コンパイル時間 | 773 ms |
コンパイル使用メモリ | 78,852 KB |
実行使用メモリ | 11,660 KB |
最終ジャッジ日時 | 2024-12-15 03:29:23 |
合計ジャッジ時間 | 6,132 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <algorithm> #include <iostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const ll mod = 1e9 + 7; ll powmod(ll a, ll e) { ll sum = 1; ll cur = a; while (e > 0) { if (e % 2) { sum = sum * cur % mod; } cur = cur * cur % mod; e /= 2; } return sum; } const int W = 1001; ll pow_memo[W][W]; ll inv_memo[W]; ll count_surj(int n, int k) { if (n < k) { return 0; } ll sum = 0; ll comb = 1; REP(i, 0, k) { sum += (pow_memo[k - i][n] * comb % mod) * (i % 2 == 0 ? 1 : mod - 1); sum %= mod; comb = comb * (k - i) % mod; comb = comb * inv_memo[1 + i] % mod; } return sum; } int main(void){ int n, m; cin >> n >> m; VI w(n); REP(i, 0, n) { cin >> w[i]; } vector<PI> e; REP(i, 0, m) { int u, v; cin >> u >> v; u--; v--; e.push_back(PI(u, v)); } REP(i, 1, W) { REP(j, 0, W) { pow_memo[i][j] = powmod(i, j); } inv_memo[i] = powmod(i, mod - 2); } // O(nm)-time ll tot = 0; REP(i, 0, n) { // retain A_k s.t. w_k >= w_i vector<VI> edges(n); for (PI uv : e) { int u = uv.first; int v = uv.second; if (w[u] >= w[i] && w[v] >= w[i]) { edges[v].push_back(u); } } // Vertices reachable to i VI reach(n, false); queue<int> que; que.push(i); while (not que.empty()) { int v = que.front(); que.pop(); if (reach[v]) { continue; } reach[v] = true; REP(j, 0, edges[v].size()) { int w = edges[v][j]; if (not reach[w]) { que.push(w); } } } REP(j, 0, n) { if (reach[j]) { tot += count_surj(w[j], w[i]); tot %= mod; } } } cout << tot << endl; }