問題C『特別講演「括弧列と塗り分け」』 : DDPC(DISCO presents ディスカバリーチャンネルプログラミングコンテスト)2016 本選

概要

きちんと対応の取れている、括弧のみからなる文字列 $S$ がある。
非負整数 $K$ が与えられたとき、以下の場合の数(を $M=10^9+7$ で割った余り)を求めよ。

$0\leq i<|S|$ のそれぞれに $x_i=\pm 1$ を割り当てる方法 $x$ のうち、以下の条件を満たすものの個数。
(条件) 任意の $i\lt j$ について、 $S_i=$ '('と $S_j=$ ')'が対応するならば、 $\displaystyle -K\leq \sum_{i\leq k\leq j}x_k\leq K$ が成立する。

制約

$2\leq |S|\leq 3000$
$0\leq K\leq 3000$

解説

問題文に「括弧の対応に矛盾がない文字列」の定義があります。
BNFで書くと、
T ::= | (T) | TT
(あるいは空文字列を除けば T ::= () | (T) | TTとも表せる)
です。これがヒントになっています。

$D(T)$ で、矛盾のない括弧列Tに対する以下のような配列を表すことにします。

$D(T)_i$ は、(条件)を満たす $T$ に対する割り当て $x$ で、 $\displaystyle \sum_{0\leq k\lt |T|}x_k=i$ を満たす者ものの個数(を $M$ で割った余り)

これは $i=0$ を中心に対称でしかも有限のところまでしか値を持ちません( $i\gt |T|$ なら $D(T)_i=0$ )。
(実際には添え字が負にならないように、ずらして管理します)

で、 $D(S)$ が求まれば、答えは $\displaystyle \sum_{0\leq i\lt |S|}D(T)_i$ が答えになります。

あとは再帰的に $D(T)$ を求めます。
以下の二つの操作を定義します。

トリミング

配列 $A$ を非負整数 $L$ でトリミングしたものは、新しい配列 $B$ であって $A$ の要素のうち $-L\leq i\leq L$ の部分だけをコピーしたもの。 $O(L)$ で求まる。

畳みこみ

二つの配列 $A,B$ の畳みこみは、新しい配列 $C$ であって、 $\displaystyle C_k=\sum_{i+j=k}A_iB_j$ を満たすもの。
$O(|A|\cdot|B|)$ で求まる。ただし、FFTを用いれば改善は可能。

すると、 $D(T)$ は以下のように求まります。

$T=（）$ のとき、 $D(T)$ は $\{1,0,2,0,1\}$ を $K$ でトリミングしたもの(これを $D_0$ とします)
$T=T_1+T_2$ のとき、 $D(T)$ は $D(T_1)$ と $D(T_2)$ の畳みこみ
$T=(T')$ のとき、 $D(T)$ は $D(T')$ と $D_0$ を畳みこんで、 $K$ でトリミングしたもの

(それ自体矛盾のない括弧列を単純にくっつけるだけなら、(条件)より単に畳みこみで済みますが、
外側に括弧がついている場合は、その外側の括弧により(条件)が発生し、トリミングが必要になります。)

再帰は $|S|$ 回程度で終わります。
各段階での仕事は畳みこみが一番重く、最悪だと $S$ の半分をくっつけるので $O(|S|^2)$ かかりますが、
最悪の場合はそんなに発生しない(なぜなら、畳みこみは結合でのみ発生し、半分ずつにするなら $O(\log N)$ 回しか畳み込めない)ので、
実際は $O(|S|^2\log N)$ 程度だと思います(多分定数倍も軽い)。
計算量の解析は結構面倒くさそうですね。

もちろん、FFTを使えばもっと早くなりますが、今回は必要ないです。

ソースコード

using System;
using System.Collections.Generic;
class Program
{
	const long M = 1000000007;
	static int F() { return int.Parse(Console.ReadLine()); }
	static string S;
	static int K;
	static long[] D0;
	// '('に対応する')'の位置
	static int[] toji;
	static void Main()
	{
		S = Console.ReadLine();
		K = F();
		var stack = new Stack<int>();
		toji = new int[S.Length];
		for (var i = 0; i < S.Length; i++)
		{
			if (S[i] == '(') stack.Push(i);
			else toji[stack.Pop()] = i;
		}
		D0 = Trim(new long[] { 1, 2, 1 }, K / 2);
		var ans = 1L;
		for (var i = 0; i < S.Length; i = toji[i] + 1)
		{
			var calc = D(i, toji[i] + 1);
			var sum = 0L;
			for (var j = 0; j < calc.Length; j++) sum = (sum + calc[j]) % M;
			ans = (ans * sum) % M;
		}
		Console.WriteLine(ans);
	}
	static long[] D(int left, int right)
	{
		if (right - left == 2) return D0;
		else if (toji[left] != right - 1) return Convolution(D(left, toji[left] + 1), D(toji[left] + 1, right));
		else return Trim(Convolution(D(left + 1, right - 1), D0), K / 2);
	}
	static long[] Convolution(long[] a, long[] b)
	{
		var A = a.Length / 2;
		var B = b.Length / 2;
		var C = A + B;
		var c = new long[2 * C + 1];
		for (var i = -A; i <= A; i++)
			for (var j = Math.Max(-B, -i - C); j <= Math.Min(B, C - i); j++)
				c[i + j + C] = (c[i + j + C] + (a[i + A] * b[j + B]) % M) % M;
		return c;
	}
	static long[] Trim(long[] a, int L)
	{
		var A = a.Length / 2;
		if (L >= A) return a;
		var b = new long[2 * L + 1];
		for (var i = -L; i <= L; i++) b[i + L] = a[i + A];
		return b;
	}
}