結果
問題 |
No.329 全射
|
ユーザー |
|
提出日時 | 2016-09-16 06:45:43 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 894 bytes |
コンパイル時間 | 1,037 ms |
コンパイル使用メモリ | 36,152 KB |
実行使用メモリ | 5,632 KB |
最終ジャッジ日時 | 2024-11-17 06:25:06 |
合計ジャッジ時間 | 2,283 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:25:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:27:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | scanf("%d", &w[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:31:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 31 | scanf("%d%d", &a, &b); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <algorithm> #define rep(i, n) for(int i = 0; i < (n); ++i) using namespace std; typedef long long ll; const int mod = 1e9 + 7; int add(int a, int b){ return (a + b) % mod; } int mul(int a, int b){ return ll(a) * b % mod; } int n, m; int w[200]; int p[200][200]; int s[1001][1001]; int main(){ scanf("%d%d", &n, &m); rep(i, n){ scanf("%d", &w[i]); } rep(i, m){ int a, b; scanf("%d%d", &a, &b); --a; --b; p[a][b] = min(w[a], w[b]); } rep(i, n){ p[i][i] = w[i]; } rep(k, n){ rep(i, n){ rep(j, n){ p[i][j] = max(p[i][j], min(p[i][k], p[k][j])); } } } s[0][0] = 1; for(int i = 1; i <= 1000; ++i){ rep(j, i + 1){ s[i][j] = mul(j, add(s[i - 1][j], s[i - 1][j - 1])); } } int ans = 0; rep(i, n){ rep(j, n){ if(p[i][j] >= w[j]){ ans = add(s[w[i]][w[j]], ans); } } } printf("%d\n", ans); return 0; }