GYM101915K Chess Positions

Description

一串01串，将其分成多个（可以为1）个区间，分别求和，要求所得的串是回文的。求总的种类数，结果对1e9+7取模

Input

The first line contains a single integer T denoting the number of test cases.

Each test case consists of one line which contains the original sequence of zeros and ones.

The length of every sequence is less than or equal to 50.

Output

For each test print one line containing one integer, the number of different ways to divide the original sequence leading to a sumindrome sequence modulo (1e9+7).

Sample Input

2
0110
1001

Sample Output

4
8

Note

The ways of dividing the sequence in the second sample are:

1001. -> 2

(1)(001) -> 1, 1

(100)(1) -> 1, 1

(10)(01) -> 1, 1

(1)(00)(1) -> 1, 0, 1

(1)(0)(01) -> 1, 0, 1

(10)(0)(1) -> 1, 0, 1

(1)(0)(0)(1) -> 1, 0, 0, 1

思路：
回文数的要求就是从左和从右一样，那么从左开始和从右开始的总值一样时，就把这些值合并，再求剩下里面的回文的种类数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e9+7;
char a[60];
int dp[60][60];

void init()
{
    memset(dp,-1,sizeof(dp));
}

ll dfs(int l,int r)
{
    //cout<<l<<' '<<r<<'\n';
    if(l>=r) return dp[l][r]=1;
    if(dp[l][r]!=-1) return dp[l][r];
    int &tent=dp[l][r]=1;//这一块全部加起来作为中间项必定正确 
    int suml=0;
    for(int i=l;i<r;i++)
    {
        suml+=a[i]-'0';
        int sumr=0;
        for(int j=r;j>i;j--)
        {
            sumr+=a[j]-'0';
            if(suml<sumr) break;
            if(suml==sumr) tent=(tent+dfs(i+1,j-1))%maxn;
        }
    }
    return tent;
}

int main()
{
    //freopen("text.txt","r",stdin);
    int t;
    cin>>t;
    while(t--)
    {
        init();
        scanf("%s",a);
        printf("%lld\n",dfs(0,strlen(a)-1));
    }
}