結果

問題 No.391 CODING WAR
コンテスト
ユーザー fjafjafja
提出日時 2017-09-23 01:10:11
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 1,829 bytes
コンパイル時間 3,767 ms
コンパイル使用メモリ 77,992 KB
実行使用メモリ 835,408 KB
最終ジャッジ日時 2024-11-08 16:27:53
合計ジャッジ時間 6,463 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1 -- * 2
other -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;

public class N391
{
	static long beki=(long)Math.pow(10, 9)+7;
	static long ans=0,n;
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		n=sc.nextLong();
		int end=0;
		long m=sc.nextLong();
		long[] h=new long[(int)m];
		long ans=0;

		if(n<m){System.out.println(0);end++;}
		else if(n==m){System.out.println(factrial(n));end++;}
		else
		{
			long rem=m-n;//振り分ける数
			hchange(h,rem);
		}
		if(end==0)
		{
			System.out.println(ans%beki);
		}
	}

	static void hchange(long[] h,long rem)
	{
		if(rem==0)
		{
			if(issyoujun(h)){ans=(ans+hairetu(h)*hairetunarabe(h,n))%beki;
}
			return;
		}
		for(int i=0;i<h.length;i++)
		{
			h[i]++;
			hchange(h,rem-1);
		}
	}

	static boolean issyoujun(long[] h)//配列が昇順かを判定
	{
		long pre=-1;
		for(int i=0;i<h.length;i++)
		{
			if(pre>h[i]){return false;}
			pre=h[i];
		}
		return true;
	}
	static void syokika(long[] h)
	{
		for(int i=0;i<h.length;i++)
		{
			h[i]=1;
		}
	}
	static long hairetunarabe(long[] h,long n)
	{
		long ans=1;
		long l=h.length;
		for(int i=0;i<h.length;i++)
		{
			ans=(ans*ncm(n,h[i]))%beki;
			n-=h[i];
		}
		return ans;
	}

	static long hairetu(long[] h)//昇順に並んだ配列ｈの並べ方数を返す。
	{
		long pre=0,cnt=1,under=1,over=1;
		for(int i=0;i<h.length;i++)
		{
			over*=(i+1)%beki;
			if(pre==h[i]){cnt++;}
			else{under=under*factrial(cnt)%beki;cnt=1;}
			pre=h[i];
		}
		return over/under;
	}



	static long factrial(long n)//nの階乗を返す。
	{
		long ans=1;
		for(int i=1;i<=n;i++)
		{
			ans*=i;
		}
		return ans%beki;
	}

	static long ncm(long n,long m)//組み合わせｎCｍを返す。
	{
		long ans=1;
		for(long i=0;i<m;i++)
		{
			ans=ans*(n-i)%beki;
		}
		for(int i=(int)m;i>0;i--)
		{
			ans/=i;
		}
		return ans%beki;
	}

}
0