結果
問題 | No.329 全射 |
ユーザー |
![]() |
提出日時 | 2019-01-26 19:34:08 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 1,489 bytes |
コンパイル時間 | 695 ms |
コンパイル使用メモリ | 97,876 KB |
実行使用メモリ | 19,392 KB |
最終ジャッジ日時 | 2024-09-17 12:18:35 |
合計ジャッジ時間 | 3,501 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> using namespace std; typedef long long int ll; typedef pair<int, int> P; const ll MOD=1e9+7; int n, m; int w[200]; vector<int> g[200]; ll comb[1001][1001], pw[1001][1001]; void calc(){ comb[0][0]=comb[1][0]=comb[1][1]=1; for(int i=2; i<=1000; i++){ comb[i][0]=comb[i][i]=1; for(int j=1; j<i; j++){ comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%MOD; } } for(ll i=0; i<=1000; i++){ pw[i][0]=1; for(int j=1; j<=1000; j++){ pw[i][j]=pw[i][j-1]*i%MOD; } } } bool used[200]; void dfs(int x, int w0){ used[x]=1; for(auto y:g[x]){ if(w[y]<w0) continue; if(used[y]) continue; dfs(y, w0); } } ll count(int w1, int w2){ ll ret=0; for(int i=0; i<w2; i++){ if(i&1){ ret-=(comb[w2][i]*pw[w2-i][w1]%MOD); ret+=MOD; }else{ ret+=(comb[w2][i]*pw[w2-i][w1]); } ret%=MOD; } return ret; } int main() { cin>>n>>m; for(int i=0; i<n; i++) cin>>w[i]; for(int i=0; i<m; i++){ int x, y; cin>>x>>y; x--; y--; g[y].push_back(x); } calc(); ll ans=0; for(int i=0; i<n; i++){ fill(used, used+n, 0); dfs(i, w[i]); for(int j=0; j<n; j++){ if(used[j]){ ans+=count(w[j], w[i]); ans%=MOD; } } } cout<<ans<<endl; return 0; }