結果

問題 No.329 全射
ユーザー ぴろず
提出日時 2015-12-22 14:39:35
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,430 bytes
コンパイル時間 2,365 ms
コンパイル使用メモリ 76,996 KB
実行使用メモリ 54,064 KB
最終ジャッジ日時 2024-09-18 18:36:50
合計ジャッジ時間 13,865 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 5 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

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