結果
問題 | 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;}