結果
問題 | No.329 全射 |
ユーザー |
|
提出日時 | 2016-10-20 21:26:13 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 538 ms / 2,000 ms |
コード長 | 1,340 bytes |
コンパイル時間 | 2,158 ms |
コンパイル使用メモリ | 81,088 KB |
実行使用メモリ | 55,744 KB |
最終ジャッジ日時 | 2024-11-22 16:52:23 |
合計ジャッジ時間 | 16,378 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
package yukicoder;import java.util.*;public class Main{public static void main(String[] args) {new Main().run();}void run() {solver();}long MOD = 1_000_000_000 + 7;void solver() {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();int[] w = new int[N];int[][] g = new int[N][N];for (int i = 0; i < N; i++) {w[i] = sc.nextInt();g[i][i] = Math.max(g[i][i], w[i]);}for (int i = 0; i < M; i++) {int src = sc.nextInt() - 1;int dst = sc.nextInt() - 1;g[src][dst] = Math.max(g[src][dst], Math.min(g[src][src], g[dst][dst]));}for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {for (int k = 0; k < N; k++) {g[j][k] = Math.max(g[j][k], Math.min(g[j][i], g[i][k]));}}}long[][] dp = new long[1001][1001];for (int i = 0; i <= 1000; i++) {dp[i][1] = 1;}for (int i = 1; i <= 1000; i++) {for (int j = 2; j <= i; j++) {dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) * j % MOD;}}long ans = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (w[j] == g[i][j]) {ans += dp[w[i]][w[j]];if (ans >= MOD)ans -= MOD;}}}System.out.println(ans);}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}