結果

問題 No.336 門松列列
コンテスト
ユーザー 37zigen
提出日時 2016-06-17 11:45:24
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,095 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 77,144 KB
実行使用メモリ 191,456 KB
最終ジャッジ日時 2024-10-09 16:48:55
合計ジャッジ時間 8,650 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().solver();
	}

	void solver() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		for (int i = 0; i < 2020; i++) {
			for (int j = 0; j < 2020; j++) {
				memo[i][j] = -1;
			}
		}
		long ans=0;
		for(int i=0;i<N;i++){
			ans=(ans+dp(i,N-i-1))%MOD;
		}
		System.out.println(2*ans%MOD);

	}

	long[][] memo = new long[2020][2020];
	final long MOD = 1000000007;

	// 戻り値:上にa個、下にb個、数字があるとき、いくつの門松列の作り方があるか。
	// ただし、上に飛ぶケースのみ考える
	// （下に飛ぶケースについては、a,bを逆転することで上に飛ぶケースに帰着）
	long dp(int a, int b) {
		if(a<0||b<0)return 0;
		if (memo[a][b] != -1)
			return memo[a][b];
		if(a==1&&b==0)return 1;
		if(a==0&&b>0)return 0;
		if(a==0&&b==0)throw new AssertionError("error");
		long sum = 0;
		for (int i = 1; i <= a; i++) {
			sum += dp(b + i - 1, a - i);
			sum%=MOD;
		}
		return memo[a][b]=sum;
	}
}
0