結果
問題 | No.329 全射 |
ユーザー |
|
提出日時 | 2017-11-07 21:58:56 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 2,602 bytes |
コンパイル時間 | 1,424 ms |
コンパイル使用メモリ | 165,108 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-11-24 04:53:06 |
合計ジャッジ時間 | 2,931 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>#define ll long long#define INF 1000000005#define MOD 1000000007#define EPS 1e-10#define rep(i,n) for(int i=0;i<(int)(n);++i)#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)#define each(a,b) for(auto (a): (b))#define all(v) (v).begin(),(v).end()#define len(v) (int)(v).size()#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())#define cmx(x,y) x=max(x,y)#define cmn(x,y) x=min(x,y)#define fi first#define se second#define pb push_back#define show(x) cout<<#x<<" = "<<(x)<<endl#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endlusing namespace std;typedef pair<int,int> P;typedef pair<ll,ll> pll;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vl;typedef vector<double> vd;typedef vector<P> vp;typedef vector<string> vs;const int MAX_N = 1005;vi G[201];ll dp[1001][1001];ll inv[MAX_N],fac[MAX_N],finv[MAX_N];void make(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for(int i=2;i<MAX_N;i++){inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;fac[i] = fac[i-1] * (ll) i % MOD;finv[i] = finv[i-1] * inv[i] % MOD;}}ll add(ll x,ll y){return (x + y)%MOD;}ll sub(ll x,ll y){return (x+MOD-y)%MOD;}ll mul(ll x,ll y){return x*y%MOD;}bool flag[MAX_N];int main(){cin.tie(0);ios::sync_with_stdio(false);int n,m;cin >> n >> m;vi vec(n);rep(i,n){cin >> vec[i];}rep(i,m){int a,b;cin >> a >> b;G[b-1].pb(a-1);}make();srep(i,1,1001){dp[i][i] = fac[i];}srep(i,1,1001){dp[i][1] = 1;}srep(i,1,1000){srep(j,1,i+1){dp[i+1][j] = mul(j,add(dp[i][j],dp[i][j-1]));}}ll ans = 0;rep(i,n){rep(j,n){flag[j] = false;}queue<int> que;flag[i] = true;que.push(i);while(!que.empty()){int p = que.front();que.pop();ans = add(ans,dp[vec[p]][vec[i]]);rep(j,len(G[p])){if(!flag[G[p][j]] && vec[G[p][j]] >= vec[i]){flag[G[p][j]] = true;que.push(G[p][j]);}}}}cout << ans << "\n";return 0;}