[区间dp]Link with Bracket Sequence II 2022杭电多校第4场 1001

Problem Description

Link has a bracket sequence of length nn. Today, Link finds out that some brackets of the sequence were lost.

Of course, he wants you to calculate how many ways are there to fill the sequence so that it will be a valid bracket sequence.

Note that there are mm types of brackets in Link's world.

Here's the definition of a valid bracket sequence:

· A sequence of length 00 is a valid bracket sequence. · If AA is a valid bracket sequence, xx is some type of left bracket, yy is the same type of right bracket, xAyxAy is a valid bracket sequence. · If A,BA,B are both valid bracket sequences, then ABAB is also a valid bracket sequence.

Input

Each test contains multiple test cases. The first line contains the number of test cases T(1 \le T \le 20)T(1≤T≤20). Description of the test cases follows.

The first line contains two integers n(1 \leq n \leq 500),m(1 \leq m < 10^9+7)n(1≤n≤500),m(1≤m<109+7), which is the length of Link's bracket sequence and the types of brackets.

The second line contains nn integers a_1,a_2,\ldots,a_n(|a_i| \leq m)a1​,a2​,…,an​(∣ai​∣≤m). The ii-th integer a_iai​ describes the ii-th character in the sequence:

· If a_i=0ai​=0, it means the bracket in this position is lost. · a_i>0ai​>0, it means the ii-th character in the sequence is the a_iai​-th type of left bracket. · a_i<0ai​<0, it means the ii-th character in the sequence is the -a_i−ai​-th type of right bracket.

It is guaranteed that there are at most 15 test cases with n>100n>100.

Output

For each test case, output one integer in a line, which is the number of ways to fill the bracket sequence so that it is a valid bracket sequence. Since the answer can be huge, just print it modulo 10^9+7109+7.

For some reason, there could be no way to make it a valid bracket sequence.

Sample Input

3

4 2

1 0 0 -1

4 2

0 0 0 -1

6 3

0 0 0 0 0 0

Sample Output

3

4

135

题意： 给出一个长度为n的括号序列，其中有若干位置为空，括号总种类为m，问有多少种不同的使括号合法的方案数。

分析： 需要两个状态数组，dp1[i][j]表示[i, j]为合法括号且i和j匹配的方案数，dp2[i][j]表示[i, j]为合法括号的方案数，然后就是一个区间dp的过程，对于区间两端点(l, r)可以枚举出合法的匹配方案数num，那么dp1[l][r]就是num*dp2[l+1][r-1]，而dp2的更新过程需要枚举断点，实际含义就是根据最后一个匹配的括号出现位置划分情况，dp2[l][r] += dp2[l][k]*dp1[k+1][r]，最后答案就是dp2[1][n]，初始化时要将区间为空集的情况置1，也就是dp[i][i-1] = 1，其余状态置0。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
 
const int mod = 1e9+7;
int dp1[505][505], dp2[505][505];
int a[505];
//dp1[i][j]表示[i, j]为合法括号且i和j匹配的方案数
//dp2[i][j]表示[i, j]为合法括号的方案数 
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, m;
		scanf("%lld%lld", &n, &m);
		for(int i = 1; i <= n; i++){
			scanf("%lld", &a[i]);
			for(int j = 1; j <= n; j++)
				dp1[i][j] = dp2[i][j] = 0;
		}
		for(int i = 2; i <= n; i++)
			dp1[i][i-1] = dp2[i][i-1] = 1;
		for(int len = 2; len <= n; len++){
			for(int l = 1; l+len-1 <= n; l++){
				int r = l+len-1;
				int num;
				if(a[l] < 0 || a[r] > 0)
					num = 0;
				else if(a[l] == 0 && a[r] == 0) 
					num = m;
				else if(a[l] != 0 && a[r] == 0 || a[l] == 0 && a[r] != 0)
					num = 1;
				else if(a[l] + a[r] == 0)
					num = 1;
				else
					num = 0;
				dp1[l][r] = dp2[l+1][r-1]*num%mod;
				dp2[l][r] = (dp2[l][r]+dp1[l][r])%mod;
				for(int k = l; k+1 <= r; k++)
					dp2[l][r] = (dp2[l][r]+dp1[l][k]*dp2[k+1][r])%mod;
			}
		}
		printf("%lld\n", dp2[1][n]);
	}
    return 0;
}