結果

問題 No.329 全射
ユーザー ぴろずぴろず
提出日時 2015-12-22 14:39:35
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,430 bytes
コンパイル時間 2,306 ms
コンパイル使用メモリ 77,432 KB
実行使用メモリ 66,532 KB
最終ジャッジ日時 2023-10-18 22:36:47
合計ジャッジ時間 7,988 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 142 ms
57,700 KB
testcase_01 AC 142 ms
57,488 KB
testcase_02 AC 143 ms
57,472 KB
testcase_03 AC 139 ms
57,524 KB
testcase_04 AC 138 ms
57,172 KB
testcase_05 AC 140 ms
57,224 KB
testcase_06 AC 141 ms
57,520 KB
testcase_07 AC 141 ms
57,516 KB
testcase_08 AC 140 ms
57,080 KB
testcase_09 AC 139 ms
57,432 KB
testcase_10 AC 138 ms
57,460 KB
testcase_11 AC 139 ms
57,084 KB
testcase_12 AC 140 ms
57,456 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no329;

import java.util.Scanner;

public class Main {
	public static final long MOD = 1000000007;
	static long[] fact = Mod.factorialArray(1000, MOD);
	static long[] factInv = Mod.factorialInverseArray(1000, MOD, Mod.inverseArray(1000, MOD));
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] w = new int[n];
		for(int i=0;i<n;i++) {
			w[i] = sc.nextInt();
		}
		int[][] d = new int[n][n];
		for(int i=0;i<n;i++) {
			d[i][i] = w[i];
		}
		for(int i=0;i<m;i++) {
			int u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			d[u][v] = w[u];
		}
		for(int k=0;k<n;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					d[i][j] = Math.max(d[i][j], Math.min(d[i][k], d[k][j]));
				}
			}
		}
//		System.out.println(Arrays.deepToString(d));
		long ans = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if (d[i][j] >= w[j]) {
					int a = w[i];
					int b = w[j];
					if (a == b) {
//						System.out.println(i + "," + j + ":" + a + "->" + b + ":" + fact[a]);
						ans += fact[a];
					}else{
						long sum = 0;
						for(int k=0;k<=b;k++) {
							long x = comb(b,k) * Mod.pow(k, a, MOD);
							if ((b - k) % 2 == 0) {
								sum += x;
							}else{
								sum += (MOD - x);
							}
						}
//						System.out.println(i + "," + j + ":" + a + "->" + b + ":" + sum % MOD);
						ans += sum;
					}
				}
			}
		}
		System.out.println(ans % MOD);
	}

	static long comb(int n,int r) {
		return fact[n] * factInv[r] % MOD * factInv[n-r] % MOD;
	}

}
class Mod {
	public static long[] factorialArray(int maxN,long mod) {
		long[] fact = new long[maxN+1];
		fact[0] = 1 % mod;
		for(int i=1;i<=maxN;i++) {
			fact[i] = fact[i-1] * i % mod;
		}
		return fact;
	}
	public static long[] inverseArray(int maxN,long modP) {
		long[] inv = new long[maxN+1];
		inv[1] = 1;
		for(int i=2;i<=maxN;i++) {
			inv[i] = modP - (modP / i) * inv[(int) (modP%i)] % modP;
		}
		return inv;
	}
	public static long[] factorialInverseArray(int maxN,long modP,long[] inverseArray) {
		long[] factInv = new long[maxN+1];
		factInv[0] = 1;
		for(int i=1;i<=maxN;i++) {
			factInv[i] = factInv[i-1] * inverseArray[i] % modP;
		}
		return factInv;
	}
	public static long pow(long a,long n,long mod) {
		long res = 1;
		while(n > 0) {
			if ((n & 1) > 0) {
				res = (res * a) % mod;
			}
			a = (a * a) % mod;
			n/=2;
		}
		return res;
	}
}
0