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