結果
問題 |
No.329 全射
|
ユーザー |
![]() |
提出日時 | 2020-06-23 22:13:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 248 ms / 2,000 ms |
コード長 | 1,858 bytes |
コンパイル時間 | 824 ms |
コンパイル使用メモリ | 86,600 KB |
実行使用メモリ | 34,956 KB |
最終ジャッジ日時 | 2024-07-03 19:33:53 |
合計ジャッジ時間 | 5,896 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
main.cpp:14:4: warning: built-in function 'pow' declared as non-function [-Wbuiltin-declaration-mismatch] 14 | ll pow[N_MAX][N_MAX]; | ^~~
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> #define N_MAX 2002 using namespace std; typedef long long ll; ll inv[N_MAX],fac[N_MAX],finv[N_MAX]; ll pow[N_MAX][N_MAX]; const ll MOD = 1000000007; void init(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i<N_MAX;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; } for(int i=1;i<N_MAX;i++){ pow[i][0] = 1; for(int j=1;j<N_MAX;j++){ pow[i][j] = (pow[i][j-1]*i)%MOD; } } } ll comb(ll n, ll r){ ll ans; if(n < r){ ans = 0; }else{ ans = (fac[n]*finv[r])%MOD; ans = (ans*finv[n-r])%MOD; ans = (ans+MOD)%MOD; } return ans; } vector<int> G[200]; int w[200]; int N, M; bool used[200]; void clear(){ for(int i = 0; i < N; i++) used[i] = false; } ll ans; ll calc(int n, int m){ ll ret = 0; // i個使わない for(int i = 0; i < m; i++){ int sgn = i%2 == 0 ? 1 : -1; ret += (sgn*comb(m, i)*pow[m-i][n])%MOD; ret %= MOD; } // cout << "calc(" << n << ", " << m << ") = " << (ret+MOD)%MOD << endl; return (ret+MOD)%MOD; } void dfs(int v,int r){ used[v] = true; ans += calc(w[v], w[r]); ans %= MOD; for(int to : G[v]){ if(!used[to] && w[to] >= w[r]) dfs(to, r); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; init(); cin >> N >> M; for(int i = 0; i < N; i++) cin >> w[i]; for(int i = 0; i < M; i++){ int u, v; cin >> u >> v; u--; v--; G[v].push_back(u); } for(int i = 0; i < N; i++){ dfs(i, i); clear(); } cout << ans << endl; }