結果
問題 | No.329 全射 |
ユーザー |
|
提出日時 | 2016-06-22 08:04:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 308 ms / 2,000 ms |
コード長 | 3,692 bytes |
コンパイル時間 | 1,950 ms |
コンパイル使用メモリ | 184,712 KB |
実行使用メモリ | 7,680 KB |
最終ジャッジ日時 | 2024-10-11 19:15:55 |
合計ジャッジ時間 | 5,538 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;template<int MOD>class ModInt{public:ModInt():value(0){}ModInt(int val):value(val<0?MOD+val%MOD:val%MOD){ }ModInt& operator+=(ModInt that){value = value+that.value;if(value>=MOD)value-=MOD;return *this;}ModInt& operator-=(ModInt that){value -= that.value;if(value<0)value+=MOD;return *this;}ModInt& operator*=(ModInt that){value = (int)((long long)value * that.value % MOD);return *this;}ModInt &operator/=(ModInt that){return *this *= that.inverse();}ModInt operator+(ModInt that) const{return ModInt(*this)+=that;}ModInt operator-(ModInt that) const{return ModInt(*this)-=that;}ModInt operator*(ModInt that) const{return ModInt(*this)*=that;}ModInt operator/(ModInt that) const {return ModInt(*this) /= that;}ModInt operator^(long long k) const{ModInt n = *this, res = 1;while(k){if(k & 1)res *= n;n *= n;k >>= 1;}return res;}ModInt inverse() const {long long a = value, b = MOD, u = 1, v = 0;while(b) {long long t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}return ModInt((int)u);}int toi() const{ return value; }private:int value;};typedef ModInt<1000000007> mint;ostream& operator<<(ostream& os, const mint& x){os << x.toi();return os;}template <class Val>vector<Val> factorials(int n){vector<Val> res(n + 1);res[0] = res[1] = 1;for(int i = 2; i <= n; ++i)res[i] = res[i - 1] * i;return res;}mint nCr(int n, int r, const vector<mint> &fact){return fact[n] / (fact[r] * fact[n - r]);}template<class Val>vector<vector<Val>> StirlingSecond(int n){vector<vector<Val>> res(n + 1, vector<Val>(n + 1));for(int i = 1; i <= n; ++i)res[i][i] = res[i][1] = 1;for(int m = 3; m <= n; ++m)for(int k = 2; k < m; ++k)res[m][k] = res[m - 1][k - 1] + res[m - 1][k] * k;return res;}const int MAX = 1000;mint solve(vector<vector<int>> G, vi &num, vector<mint> &fact){auto S = StirlingSecond<mint>(MAX);int V = (int)G.size();mint res = 0;for(int u = 0; u < V; ++u){priority_queue<pii> que;vi vis(V);que.push(mp(num[u], u));while(que.size()){int mini, v;tie(mini, v) = que.top();que.pop();if(vis[v]++)continue;if(mini >= num[v])res += S[num[u]][num[v]] * fact[num[v]];for(int w : G[v])if(!vis[w])que.push(mp(min(mini, num[v]), w));}}return res;}int main(){ios::sync_with_stdio(0);cin.tie(0);int N, M;auto fact = factorials<mint>(MAX);cin >> N >> M;vi w(N);rep(i, N)cin >> w[i];vector<vi> G(N);rep(i, M){int u, v;cin >> u >> v;--u;--v;G[u].push_back(v);}cout << solve(G, w, fact) << endl;}