結果
問題 | No.329 全射 |
ユーザー | kuuso1 |
提出日時 | 2015-12-22 02:21:32 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,152 ms / 2,000 ms |
コード長 | 2,440 bytes |
コンパイル時間 | 2,649 ms |
コンパイル使用メモリ | 115,324 KB |
実行使用メモリ | 38,272 KB |
最終ジャッジ日時 | 2024-09-18 18:28:17 |
合計ジャッジ時間 | 15,489 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ int[][] WF=new int[N][]; for(int i=0;i<N;i++){ WF[i]=new int[N]; } for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(i==j||Mp[i,j])WF[i][j]=Math.Min(A[i],A[j]); } } for(int k=0;k<N;k++){ for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ WF[i][j]=Math.Max(WF[i][j],Math.Min(WF[i][k],WF[k][j])); } } } for(int j=0;j<N;j++){ for(int i=0;i<N;i++){ if(WF[i][j]<A[j])WF[i][j]=0; } } long mod=(long)1e9+7; long[][] nCr=new long[1001][]; for(int i=0;i<=1000;i++)nCr[i]=new long[1001]; nCr[0][0]=1; for(int i=1;i<=1000;i++){ for(int j=0;j<=i;j++){ nCr[i][j]=j==0?1:nCr[i-1][j-1]+nCr[i-1][j]; if(nCr[i][j]>=mod)nCr[i][j]-=mod; } } long[][] iPown=new long[1001][]; for(int i=0;i<1001;i++){ iPown[i]=new long[1001]; iPown[i][0]=1; for(int j=1;j<=1000;j++){ iPown[i][j]=iPown[i][j-1]*i; if(iPown[i][j]>=mod)iPown[i][j]%=mod; } } long ans=0; for(int ii=0;ii<N;ii++){ for(int jj=0;jj<N;jj++){ if(WF[ii][jj]==0)continue; //A[i] -> A[j] surj: // n->k surj:Σ(-1)^{k-i}*kCi*i^n, i=1 to k int n=A[ii]; int k=A[jj]; long surj=0; for(int i=1;i<=k;i++){ long term=nCr[k][i]*iPown[i][n]; if(term>=mod)term%=mod; if((k-i)%2==0)surj+=term; if((k-i)%2!=0)surj+=mod-term; if(surj>=mod)surj%=mod; } ans+=surj; if(ans>=mod)ans%=mod; } } Console.WriteLine(ans); } int N,M; int[] A; bool[,] Mp; public Sol(){ var d=ria(); N=d[0];M=d[1]; A=ria(); Mp=new bool[N,N]; for(int i=0;i<M;i++){ d=ria(); Mp[d[0]-1,d[1]-1]=true; } } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(){return Console.ReadLine().Split(' ');} static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));} static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));} static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));} }