[白俊]#10422かっこ

9667 ワード
白駿 カタラン数 algorithm DP テキストリンク

質問する


「(」,「)」文字のみからなる文字列を括弧文字列と呼ぶ.カッコ文字列の定義は次のとおりです.()は、正しいかっこ文字列です.Sが正しい括弧文字列であれば、(S)も正しい括弧文字列である.SとTが正しい括弧文字列である場合、2つの文字列を接続するSTも正しい括弧文字列である.()()()は有効な括弧文字列ですが、()は有効な括弧文字列ではありません.かっこ文字列が正しいかどうかを決定する方法はいくつかあります.
しかし、私たちが知りたいのは、長さLの正しい括弧文字列の個数です.長さLの異なる右かっこ文字列の数を出力するプログラムを作成します.

入力


第1行は、試験用例の個数を示すT(1≦T≦100)を与える.2行目から、各テスト例にはLがあり、カッコ文字列の長さを表します.(1 ≤ L ≤ 5000)

しゅつりょく


各テストケースについて、有効な括弧長Lの括弧文字列数を10000007の残りの部分で除算します.

入力例1

3
1
2
4

サンプル出力1

0
1
2

に答える


この問題は動的プログラミングアルゴリズムで解決できる.この問題を解決するためには、カタラン数を知る必要がある.
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static long[] dp;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        dp = new long[5001];
        dp[0] = 1;
        dp[1] = 1;

        for(int i=2; i<=5000; i++)
            dp[i] = sol(0, i-1)%(1000000007);

        for(int i=0; i<T; i++) {
            int n = Integer.parseInt(br.readLine());

            if(n%2!=0)
                System.out.println(0);
            else
                System.out.println(dp[n/2]%(1000000007));
        }

    }

    public static long sol(int n, int m) {
        if(m==0)
            return (dp[n]*dp[0])%(1000000007);

        return (dp[n]*dp[m])+sol(n+1, m-1)%(1000000007);
    }
}
ZK Demoトップページレイアウトコード
Reactはクリックドラッグ機能onDragを実現