ARC059F バイナリハック(800)

$0$ か $1$ を末尾に挿入,末尾削除をする操作を $N$ 回行って、最終的に文字列 $S$ にする操作列の場合の数を求める問題。 $1 \leq N \leq 5000$ と大きい。

解法

実は、同じ長さの文字列であれば操作列の場合の数は全て同じになる。
なぜなら、操作において、$0$, $1$ の挿入は任意で選べるため、常に文字列に則した文字( $i$ 番目の文字 $c$ を挿入するとき $S_i = c$ であるようなもの)を入れることができるし、そうでない文字も入れることが出来るからである。

ということは、 $|S|$ 文字の任意の文字列を作る場合の数を求めてあげて、それを $2^{|S|}$ で割った数を求めれば良くなる。(補足: $2^{|S|}$ とはそれぞれ異なる $|S|$ 文字の文字列のパターン数である)

$|S|$ 文字の任意の文字列を作る場合の数は、$DP[n][x]$( $n$ 回操作した時に文字列の長さが $x$ であるような場合の数)を求めることで解くことが出来る。

ソースコード

余りの世界で割り算をするときには、逆元を求めるために「フェルマーの小定理」もしくは「拡張ユークリッド互除法」を使用するのでその部分は押さえておいていただけるとありがたいです。
ここでは説明を省略します。

Modint<mod> dp[5005][5005];
 
int main() {
    int N;
    string S;
    cin >> N >> S;
    dp[0][0] = 1;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N; j++) {
            dp[i + 1][j + 1] += dp[i][j] * Modint<mod>(2);
            dp[i + 1][max(0, j - 1)] += dp[i][j];
        }
    }
 
    cout << dp[N][S.size()] / (Modint<mod>(2)^(((uint64_t)S.size()))) << el;
    
    return (0);
}