Cerinta completa

Shashank loves strings, but he loves palindromic strings the most. He has a list of strings, , where each string, , consists of lowercase English alphabetic letters. Shashank wants to count the number of ways of choosing non-empty subsequences such that the following conditions are satisfied:

  1. is a subsequence of string , is a subsequence of string , is a subsequence of string , , and is a subsequence of string .
  2. is a palindromic string, where + denotes the string concatenation operator.

You are given queries where each query consists of some list, . For each query, find and print the number of ways Shashank can choose non-empty subsequences satisfying the criteria above, modulo , on a new line.

Note: Two subsequences consisting of the same characters are considered to be different if their characters came from different indices in the original string.

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query in the following format:

  • The first line contains an integer, , denoting the size of the list.
  • Each line of the subsequent lines contains a non-empty string describing .

Constraints

  • over a test case.

For of the maximum score:

  • over a test case.

Output Format

For each query, print the number of ways of choosing non-empty subsequences, modulo , on a new line.

Sample Input 0

3
3
aa
b
aa
3
a
b
c
2
abc
abc

Sample Output 0

5
0
9

Explanation 0

The first two queries are explained below:

  1. We can choose the following five subsequences:

    1. , , , where is the first character of and is the first character of .
    2. , , , where is the second character of and is the second character of .
    3. , , , where is the first character of and is the second character of .
    4. , , , where is the second character of and is the first character of .
    5. , ,

    Thus, we print the result of on a new line.

  2. There is no way to choose non-empty subsequences such that their concatenation results in a palindrome, as each string contains unique characters. Thus, we print on a new line.

Limbajul de programare folosit: cpp14

Cod:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<cstring>
using namespace std;
const int MOD=1e9+7;

string s[50];
int dp[1001][1001];
int dpsum[1001][1001];
vector<int> len;
vector<int> lenSum;

void solve(string t,int n){
    memset(dp,0,sizeof(dp));
    memset(dpsum,0,sizeof(dpsum));
    int l=t.size();
    for(int k=1;k<=l;k++){
        for(int i=0;i+k-1<l;i++){
            if(k==1){
                dp[i][i]=1;
                dpsum[i][i]=1;
            }
            else{
                int j=i+k-1;                    
                int thisI=(lower_bound(lenSum.begin(),lenSum.end(),i+1)-lenSum.begin());
                int thisJ=(lower_bound(lenSum.begin(),lenSum.end(),j+1)-lenSum.begin());
                if(t[i]==t[j]) {
                    dp[i][j]=dpsum[i+1][j-1];
                    
                    if(thisI==thisJ) dp[i][j]=(dp[i][j]+1)%MOD;
                    else{
                        if(i+1!=lenSum[thisI])dp[i][j]=(dp[i][j]+dpsum[lenSum[thisI]][j-1])%MOD;
                        
                        if(j!=lenSum[thisJ-1])dp[i][j]=(dp[i][j]+dpsum[i+1][lenSum[thisJ-1]-1])%MOD;
                        
                        if((i+1!=lenSum[thisI])&&(j!=lenSum[thisJ-1]))dp[i][j]=(dp[i][j]+dpsum[lenSum[thisI]][lenSum[thisJ-1]-1])%MOD;
                        if(thisI+1==thisJ) dp[i][j]=(dp[i][j]+1)%MOD;
                        
                    }
                }
                int nextI=(lower_bound(lenSum.begin(),lenSum.end(),i+1+1)-lenSum.begin());
                int prevJ=(lower_bound(lenSum.begin(),lenSum.end(),j+1-1)-lenSum.begin());
                if(nextI==thisI && prevJ==thisJ){
                    dpsum[i][j]=(dpsum[i+1][j]+dpsum[i][j-1])%MOD;
                    dpsum[i][j]=(dpsum[i][j]-dpsum[i+1][j-1])%MOD;
                    dpsum[i][j]=(dpsum[i][j]+dp[i][j])%MOD;
                }
                else if(nextI==thisI){
                   
                    dpsum[i][j]=(dpsum[i+1][j]+dp[i][j])%MOD;
                }
                else if(prevJ==thisJ){
                    
                    dpsum[i][j]=(dpsum[i][j-1]+dp[i][j])%MOD;
                }
                else{
                   
                    dpsum[i][j]=dp[i][j];
                }
                
            }
        }
    }
    if(dpsum[0][l-1]<0) dpsum[0][l-1]+=MOD;
    cout<<dpsum[0][l-1]<<endl;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int _test;
    cin>>_test;
    while(_test--){
        int n;
        cin>>n;
        string total="";
        len.clear();
        lenSum.clear();
        lenSum.push_back(0);
        for(int i=0;i<n;i++){
            cin>>s[i];
            total.append(s[i]);
            len.push_back(s[i].size());
            lenSum.push_back(lenSum[i]+len[i]);
        }
        
        solve(total,n);
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464649077

Link challenge: https://www.hackerrank.com/challenges/shashank-and-palindromic-strings/problem

Shashank and the Palindromic Strings