結果
問題 | No.758 VVVVV |
ユーザー |
|
提出日時 | 2019-01-06 18:24:52 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,007 ms / 2,000 ms |
コード長 | 1,098 bytes |
コンパイル時間 | 2,194 ms |
コンパイル使用メモリ | 77,312 KB |
実行使用メモリ | 69,256 KB |
最終ジャッジ日時 | 2024-10-14 01:56:36 |
合計ジャッジ時間 | 17,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import java.io.*;import java.util.*;public class Main{final long mo=(long)1e9+7;public static void main(String[] args){new Main().run();}void run(){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int[] deg=new int[N];for(int i=0;i<N-1;++i){int a=sc.nextInt();int b=sc.nextInt();--a;--b;++deg[a];++deg[b];}if(N==1){System.out.println(1);return;}int n=N-1;int m=0;for(int i=1;i<N;++i){if(deg[i]==1)++m;}System.out.println(narayana(n,m));}long narayana(long n,long k){return inv(k)*comb(n,k-1)%mo*comb(n-1,k-1)%mo;}long comb(long n,long k){long ret=1;for(long i=0;i<k;++i){ret=ret*(n-i)%mo*inv(i+1)%mo;}return ret;}long inv(long a){return pow(a,mo-2);}long pow(long a,long n){long ret=1;for(;n>0;n>>=1,a=a*a%mo){if(n%2==1)ret=ret*a%mo;}return ret;}}