# Shashank and the Palindromic Strings

### Problem Statement :

```Shashank loves strings, but he loves palindromic strings the most. He has a list of n strings, A = [a0,a1,...,an-1] , where each string, ai, consists of lowercase English alphabetic letters. Shashank wants to count the number of ways of choosing non-empty subsequences s0,s1,s2,...,sn-1 such that the following conditions are satisfied:

1.s0 is a subsequence of string a0, s1 is a subsequence of string a1, s2 is a subsequence of string a2, ..., and sn-1 is a subsequence of string .
2. s-+s1+s2+ ...+ sn-1 is a palindromic string, where + denotes the string concatenation operator.
You are given q queries where each query consists of some list, A. For each query, find and print the number of ways Shashank can choose n non-empty subsequences satisfying the criteria above, modulo 10^9 + 7, 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, q, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains an integer, n, denoting the size of the list.
Each line i of the n subsequent lines contains a non-empty string describing ai.
Constraints
1 <= q <= 50
1 <= n <= 50
Σ |ai| <= 1000 over a test case.
For 40% of the maximum score:
1 <= n <= 5
Σ |ai| <= 250 over a test case.
Output Format

For each query, print the number of ways of choosing non-empty subsequences, modulo 10^9 + 7, on a new line.```

### Solution :

```                            ```Solution in C :

In C++ :

#include <bits/stdc++.h>

using namespace std;

#define vec vector
#define ALL(x) (x).begin(), (x).end()
#define mp make_pair
#define mt make_tuple

typedef pair< int, int > pii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int const inf = 1000 * 1000 * 1000;
ll const inf64 = 1ll * inf * inf;

int const mod = inf + 7;

inline int sum(int a, int b) { return (a + b) % mod; }
inline int raz(int a, int b) { return ((a - b) % mod + mod) % mod; }
inline int mul(int a, int b) { return (1ll * a * b) % mod; }

bool solve() {

int n;
cin >> n;

vec< string > a(n);
string text = "";

for(int i = 0;i < n;i++) cin >> a[i], text += a[i];

int sz = (int)text.size();

vec< int > id(sz);

for(int j = 0, i = 0;i < n;i++) {
for(int iter = 0;iter < (int)a[i].size();iter++) {
id[j++] = i;
}
}

vec< int > le(n, inf);
vec< int > ri(n,-inf);

for(int i = 0;i < sz;i++) {
le[id[i]] = min(le[id[i]], i);
ri[id[i]] = max(ri[id[i]], i);
}

vec< vec< int > > dp(sz, vec< int >(sz));
vec< vec< int > > sm(sz, vec< int >(sz));

for(int l = sz - 1;l >= 0;l--) {
for(int r = l;r < sz;r++) {
if(r > 0) sm[l][r] = sum(sm[l][r], sm[l][r - 1]);
if(l + 1 < sz) sm[l][r] = sum(sm[l][r], sm[l + 1][r]);
if(r > 0 && l + 1 < sz) sm[l][r] = raz(sm[l][r], sm[l + 1][r - 1]);

if(r < l || text[l] != text[r]) continue;

dp[l][r] = id[r] - id[l] <= 1;

int tl1, tr1, tl2, tr2;

tl1 = l + 1;
tr1 = min(r - 1, id[l] + 1 < n ? ri[id[l] + 1] : ri[id[l]]);

tl2 = max(l + 1, id[r] ? le[id[r] - 1] : le[id[r]]);
tr2 = r - 1;

if(tl1 <= tr1 && tl2 <= tr2) {
dp[l][r] = sum(dp[l][r], sm[tl1][tr2]);
if (tl2 > 0) dp[l][r] = raz(dp[l][r], sm[tl1][tl2 - 1]);
if (tr1 + 1 < sz) dp[l][r] = raz(dp[l][r], sm[tr1 + 1][tr2]);
if (tr1 + 1 < sz && tl2 > 0) dp[l][r] = sum(dp[l][r], sm[tr1 + 1][tl2 - 1]);
}

sm[l][r] = sum(sm[l][r], dp[l][r]);
}
}

int res = 0;

for(int l = 0;l < (int)a.size();l++) {
for(int r = sz - 1;r >= l && r >= sz - (int)a[n - 1].size();r--) {
res = sum(res, dp[l][r]);
}
}

cout << res << "\n";

return true;
}

int main() {

int T;
cin >> T;

while(T--) solve();

return 0;
}

In Java :

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
final static int MODE = 1000000007;
/*
* Complete the palindromicStrings function below.
*/
static int palindromicStrings(int[] a, char[] cc) {
final int N = cc.length;
int[][] dp = new int[6*N][N];
int[] ids = new int[N];
int t=a==1?0:1;
for(int i=1;i<N;++i){
if(t==0){
ids[i]=ids[i-1]+1;
}else{
ids[i]=ids[i-1];
}
++t;
if(a[ids[i]]==t)t=0;
}
int[] st = new int;
for(int i=1;i<6;++i)st[i]=i*N;
for(int i=N-1;i>=0;--i){
dp[st+i][i]=dp[st+i][i]=dp[i][i]=1;
dp[st+i][i]=dp[st+i][i]=dp[st+i][i]=2;
for(int j=i+1;j<N;++j){
if(ids[j]==ids[j-1]){
dp[st+i][j]=dp[st+i][j-1];
dp[st+i][j]=dp[st+i][j-1];
}else{
dp[st+i][j]=dp[st+i][j-1];
}
if(cc[i]==cc[j]){
if(i+1==j){
++dp[st+i][j];
++dp[st+i][j];
}else{
int k=0;
if(ids[i]==ids[i+1])k+=2;
if(ids[j]==ids[j-1])k+=1;
dp[st+i][j]=(dp[st+i][j]+dp[st[k]+i+1][j-1])%MODE;
dp[st+i][j]=(dp[st+i][j]+dp[st[k]+i+1][j-1])%MODE;
}
}
dp[st+i][j]=dp[st+i][j]=dp[st+i][j];
dp[st+i][j]=dp[st+i][j]=dp[st+i][j];
if(ids[i]==ids[i+1]){
dp[st+i][j]=(dp[st+i][j]+dp[st+i+1][j])%MODE;
dp[st+i][j]=(dp[st+i][j]+dp[st+i+1][j])%MODE;
dp[st+i][j]=(dp[st+i][j]+dp[st+i+1][j])%MODE;
dp[st+i][j]=(dp[st+i][j]+dp[st+i+1][j])%MODE;
}else{
dp[st+i][j]=(dp[st+i][j]+dp[st+i+1][j])%MODE;
dp[st+i][j]=(dp[st+i][j]+dp[st+i+1][j])%MODE;
}
}
}
return dp[N-1];
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws Exception {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
long t = System.currentTimeMillis();
int q = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

for (int qItr = 0; qItr < q; qItr++) {
int aCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

int[] a = new int[aCount];
StringBuilder sb = new StringBuilder();

for (int aItr = 0; aItr < aCount; aItr++) {
String aItem = scanner.nextLine();
//scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
a[aItr] = aItem.length();
sb.append(aItem);
}
int result = palindromicStrings(a, sb.toString().toCharArray());

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close();
System.out.println(System.currentTimeMillis()-t);
}
}

In C :

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define md 1000000007

char cv, fv, lv, gv;
unsigned int mv[1000 * 1000 * 4];
int m;

int i, j, k, l, n;
char *s;
for (i = 0; i < 1000; ++i)
{
fv[i] = 0;
lv[i] = 0;
}
s = cv;
k = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%s", s);
l = strlen(s);
fv[k] = 1;
lv[k + l - 1] = 1;
for (j = 0; j < l; ++j)
{
gv[k + j] = i;
}
k += l;
s += l;
}
m = strlen(cv);
}

int ix(int i, int j, int oi, int oj) {
return (i * m * 4) + (j * 4) + (oi * 2) + oj;
}

unsigned int f(int i, int j, int oi, int oj) {
if (i == j)
{
return (oi || oj) ? 2 : 1;
}
if (j < i)
{
return 1;
}
if (gv[i] == gv[j])
{
oi = oi || oj;
oj = oi;
}
return mv[ix(i, j, oi, oj)];
}

void run() {
int l, i, j, p;
int il, jf, oi, oj, oi1, oj1, b1, b2;
unsigned int c;
for (l = 2; l <= m; ++l)
{
for (i = 0; i <= m - l; ++i)
{
j = i + l - 1;
for (p = 0; p < 4; ++p)
{
if (p == 0 || p == 3 || gv[i] < gv[j])
{
il = lv[i];
jf = fv[j];
oi = p & 1;
oj = p >> 1;
c = 0;
b1 = oi || !il;
b2 = oj || !jf;
oi1 = !il && oi;
oj1 = !jf && oj;
if (b1)
{
c += f(i + 1, j, oi1, oj);
}
if (b2)
{
c += f(i, j - 1, oi, oj1);
}
if (b1 && b2 && (l > 2 || oi || oj))
{
c += md - f(i + 1, j - 1, oi1, oj1);
}
if (cv[i] == cv[j])
{
c += f(i + 1, j - 1, !il, !jf);
}
//printf("%d %d %d %d %u\n", i, j, oi, oj, c % md);
mv[ix(i, j, oi, oj)] = c % md;
}
}
}
}
printf("%u\n", mv[ix(0, m - 1, 0, 0)]);
}

int main() {
int q, i;
scanf("%d", &q);
for(i = 0; i < q; ++i) {
run();
}
return 0;
}```
```

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element