TPCTFに出た

テスト期間ですが、 昨日joinしたHarekazeからTPCTFに出ました。
私が解いたのは、朝起きて1限の防災リテラシーの時間で考えた20点の問題だけです(ア。

Not Lisp (Misc 20pts)

ctong610 is trying to write a program, but he's really bad at programming so his program has both syntax errors and is way too long.
If he has 10⁴ pairs of parentheses, in how many ways can they be organized validly? (Note: (()()) is valid, but (()()( is not).
Give your answer as a number mod 10³.
Note: ^ in this case is exponentiation, not xor.
The flag is just a number.

FLAGは640。

全探索だとO(2²⁰⁰⁰⁰)で無理なのでDPを使います。
"10⁴ parentheses" ではなく "10⁴ pairs of parentheses" なので、10⁴個のペア、つまり 2*10⁴ 個で考えないとダメ。

#include <iostream>
#include <queue>
#include <iomanip>
#include <map>
#include <algorithm>

using namespace std;

ll dp[20010][10010]; // dp[i][k] := i番目までで、 "("の数-")"の数 == k になる組みあわせの数

int main() {
    dp[0][0] = 1;
    for (int i = 0; i < 20000; i++) {
        for (int k = 0; k < 10010; k++) {
            dp[i+1][k+1] += dp[i][k];
            if (k>0) dp[i+1][k-1] += dp[i][k];

            dp[i+1][k+1] %= 1000;
            if (k>0) dp[i+1][k-1] %= 1000;
        }
    }

    cout << dp[20000][0] << endl;
    return 0;
}