PALMACH - Editorial

taran_1407 · September 27, 2019, 7:24am

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Rami

Tester: Roman Bilyi

Editorialist: Taranpreet Singh

DIFFICULTY:

Medium-hard

PREREQUISITES:

Dynamic Programming, Combinatorics, FFT/NTT

PROBLEM:

Given an array S of N strings of length N each and an integer M. Hasan developed a machine which takes a sequence of strings A_1, A_2, \ldots A_K and assuming A_{i, j} denotes the j-th character of i-th string, then the machine generates the string B as follows.

B_1 = A_{1, 1}, B_2 = A_{2, 1}, \ldots B_K = A_{K, 1}
B_{K+1} = A_{1, 2}, B_{K+2} = A_{2, 2}, \ldots B_{2*K} = A_{K, 2}
\ldots
B_{(N-1)*K+1} = A_{1, N}, B_{(N-1)*K+2} = A_{2, N}, \ldots B_{N*K} = A_{K, N}

Find the number of sequences of pairwise distinct K indices i_1, i_2 \ldots i_K where 1 \leq K \leq M and running the machine with strings (S_{i_1}, S_{i_2}, \ldots S_{i_K}) generates a palindrome string.

NOT-SO-QUICK EXPLANATION

For a sequence (i_1, i_2, \ldots i_k) to be valid, we need string S_{i_j} being the reverse of string S_{i_{K-j+1}}. For odd k, we need string S_{i_{(k+1)/2}} itself to be palindrome.
We can group strings into palindromes and non-palindromes, and for each non-palindrome string, we can store the frequency of the string as well as its reverse. Let’s define two types of groups, palindrome group, which stores frequency of the string, and non-palindromic groups, which stores the frequency of a string and its reverse.
Now, A Dynamic programming with state (i, sz, odd) 0 \leq odd \leq 1 denoting the number of sequences such that we have chosen 2*sz+odd strings from first i groups, considering the only fixed ordering of first sz elements.
For non-palindrome group with frequency of string and it’s reverse being x and y respectively, the DP transition is (i, sz, odd) = \displaystyle\sum_{j= 0}^{j \leq min(sz, x, y)} (i-1, sz-j, odd)*^xC_j*^yC_j*j!*2^j
For palindrome string with frequency x, the DP transitions can be given as
- (i, sz, 0) = \displaystyle\sum_{j = 0}^{j \leq min(sz, x/2)} (i-1, sz-j, 0)*^xC_j*^{x-j}C_j*j!
- (i, sz, 1) = \displaystyle\sum_{j = 0}^{j \leq min(sz, x/2)} (i-1, sz-j, 1)*^xC_j*^{x-j}C_j*j! + x*(i-1, sz, 0)*^{x-1}C_j*^{x-j-1}C_j*j!
In all three transitions, we can write the sum as product of polynomials, thereby using FFT to solve the problem.

EXPLANATION

This editorial has three parts, determining the condition for a valid sequence, secondly figuring out a slow solution, and then optimizing it using Fast Fourier Transform (optional).

Determining if a sequence is valid

Assuming K = 4 strings of length N = 3 each, Let’s write the B string.

A_{1, 1}, A_{2, 1}, A_{3, 1}, A_{4, 1}, A_{1, 2}, A_{2, 2}, A_{3, 2}, A_{4, 2}, A_{1, 3}, A_{2, 3}, A_{3, 3}, A_{4, 3}

Writing it’s reverse, we have

A_{4, 3}, A_{3, 3}, A_{2, 3}, A_{1, 3}, A_{4, 2}, A_{3, 2}, A_{2, 2}, A_{1, 2}, A_{4, 1}, A_{3, 1}, A_{2, 1}, A_{1, 1}

For B to be a palindrome, we need A_{1,1} = A_{4, 3}, A_{2, 1} = A_{3, 3}, A_{3, 1} = A_{2, 3}, A_{4, 1} = A_{1, 3}, A_{1, 2} = A_{4, 2} and A_{2, 2} = A_{3, 2}

Rearranging these, we have, A_{1, 1} = A_{4, 3}, A_{1, 2} = A_{4, 2} and A_{1, 3} = A_{4, 1} which implies that string S_4 should be reverse of string S_1.

Similarly, we can prove that we need S_3 to be reverse to S_2.

Generalizing this, we can say that for the string B to be a palindrome, we need S_{K-i+1} to be reverse of string S_{i}. Also, when K is odd, we need string S_{(K+1)/2} to be reverse of string S_{(K+1)/2} which implies that if K is odd, S_{(K+1)/2} should be a palindrome.

So, for each palindrome, we can maintain it’s frequency, and for each non-palindrome string, we can maintain the frequency of both the string and its reverse.

Counting the number of sequences

Now, let us consider each group one by one (We can consider groups in any order). We can use Dynamic Programming here, with DP state being (i, sz, odd) where

i denote the number of groups considered till now.
sz denote the number of strings chosen to be included in B divided by 2 (Not including middle string).
odd denote whether we have a palindrome string at the middle of B or not. 0 \leq odd \leq 1 holds.

Base case:
Consider empty sequence first, we can see, that there’s one way, so we have DP_{(0, 0, 0)} = 1.
Transitions:
Let us assume DP_{(i-1, sz, odd)} is already calculated for all sz and odd and we want to evaluate DP_{(i, sz, odd)} for all sz and odd. Two cases arise.

If the next group is a non-palindrome group
In this case, Current group has the string appears x times and it’s reverse appear y times.

Suppose we are choosing j pairs of strings, each pair containing the original string and it’s reverse each. The number of ways of choosing j strings from x strings is ^xC_j and number of ways of choosing j strings from y strings is ^yC_j. So total {^xC_j}*{^yC_j} ways to choose strings which appear in pairs.

Now, to count the number of pairs, we need to see how we can choose pairs two sets each of size j such that each string appears in exactly one pair. Each string in the first set can be paired to any of the remaining strings, which gives us j! ways to make pairs. Lastly, since here we have Pair (a, b) not equivalent to pair (b, a), this further gets multiplied by 2^j, resulting in {^xC_j}*{^yC_j}*j!*2^j ways.

Hence, DP_{i, sz, odd} = \displaystyle\sum_{j = 0}^{j \leq min(sz, x, y)} DP_{(i-1, sz-j, odd)}*{^xC_j}*{^yC_j}*j!*2^j

Since this string is non-palindrome, it cannot be chosen as the middle string of B.

If unclear on this, refer example

Consider first set [a, b, c] and second set [d, e, f] where a, b, c, d, e, f denote the indices.
We have 3! = 6 ways to make pairs

(a, d), (b, e), (c, f)
(a, d), (b, f), (c, e)
(a, e), (b, d), (c, f)
(a, e), (b, f), (c, d)
(a, f), (b, d), (c, f)
(a, f), (b, e), (c, d)

Lastly, for each of the above way, we have considered pair (p, q) to be same as (q, p), which is not the case in our problem, so each pair can appear in two ways giving 2^j ways for each above pairings.

If the next group is palindrome
Assume a palindrome string appearing x times, we can select j strings to appear in left half in ^xC_j ways, j strings from remaining x-j strings to appear in right half in ^{x-j}C_j ways, and the number of ways to make pairs is j! (Factor 2^j does not appear here, since both sets are chosen from the same set of x strings, and not different sets)

So, we have D_{(i, sz, 0)} = \displaystyle\sum_{j = 0}^{2*j \leq x, j \leq sz}DP_{(i-1, sz-j, 0)}*{^xC_j}*{^{x-j}C_j}*j!

Now, for DP_{(i, sz, 1)}, Either previous we have chosen middle string one of the previous i-1 groups, or we choose middle in this group.

Transition with not choosing middle string from current group is same in idea as for DP_{i, sz, 0} If middle is chosen from this group, it’s index can be chosen in x ways, and after that, j indices to appear in left half can be chosen in ^{x-1}C_j ways and then we can choose indices to appear in right half in ^{x-j-1}C_j ways. Making pair for each way of choosing is j!, giving us the following recurrence for DP_{(i, sz, 1)}

DP_{(i, sz, 1)} = \displaystyle\sum_{j = 0}^{2*j \leq x, j \leq sz} DP_{(i-1, sz, 1)}* {^xC_j}*{^{x-j}C_j}*j! + x*DP_{(i-1, sz-j, 0)}*{^{x-1}C_j}*{^{x-1-j}C_j}*j!

That’s it, computing the number of ways this way, if n is the number of groups, the final answer is \displaystyle\sum_{j = 0} DP_{(n, i, 0)}*i!+DP_{(n, i, 1)}*i! (Since left indices can also appear in any order, and exclude the empty subsequence.

This solution is of the complexity of order O(n*M^2) since for each state, time taken is O(M) and there are (n*M) states though this solution runs fast in practice since the sum of degrees of P and$Q$ does not exceed 2*M.

Speedup using FFT/NTT

Let’s rearrange states of DP to be (i, odd, sz) and assume DP_{(i, odd)} represent a polynomial where coefficient of x^{sz} in this polynomial denote DP_{(i, sz, odd)}

For a non-palindrome group withfrequency of string and it’s reverse being x and y, we can write another polynomial P(x) = p_0+p_1*x \ldots p_{min(x, y)}*x^{min(x, y)} where p_j = {^xC_j}*{^yC_j}*j!*2^j

We can see, that DP_{(i, odd)} = DP_{(i-1, odd)}*P(x) holds.

For a palindrome group with frequency x, Let’s write two polynomials P(x) such that p_j = {^xC_j*{^{x-j}C_j}*j!} and q_j =x*{^{x-1}C_j*{^{x-1-j}C_j}*j!}

We can see that DP_{(i, 0)} = DP_{(i-1, 0)}*P(x) and DP_{i, 1} = DP_{(i-1, 0)}*Q(x)+DP_{(i-1, 1)}*P(x)

We can compute these products using Fast Fourier Transformation as nicely explained here

TIME COMPLEXITY

Using FFT, the time complexity is O(N*M*log(M)) per test case.

SOLUTIONS:

Setter's Solution

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 400007;

const int MOD = 1000000007;

const double Pi = acos(-1.0);

Int F[MAX];
Int IF[MAX];

Int bpow(Int a, Int k)
{
	Int res = 1;
	while (k) {
	    if (k & 1) {
	        res *= a;
	        res %= MOD;
	    }
	    a *= a;
	    a %= MOD;
	    k /= 2;
	}
	return res;
}

Int C(int n, int k)
{
	return F[n] * IF[k] % MOD * IF[n - k] % MOD;
}

Int pw2[MAX];

typedef complex<double> base;
const int LEN = 1<<17; // max length, power of 2
base PW[LEN]; // LEN-th roots of -1
void fft(vector<base>& a, bool invert)
{
	int lg = 0;
	while((1<<lg) < SZ(a)) lg++;
	FOR (i, 0, SZ(a))
	{
	    int x=0;
	    FOR (j, 0, lg)
	        x |= ((i>>j)&1)<<(lg-j-1);
	    if(i<x)
	        swap(a[i], a[x]);
	}
	for (int len = 2; len <= SZ(a); len *= 2)
	{
	    int diff = LEN / len;
	    if (invert) diff = LEN - diff;
	    for (int i = 0; i < SZ(a); i += len)
	    {
	        int pos = 0;
	        FOR (j, 0, len/2)
	        {
	            base v = a[i+j];
	            base u = a[i+j+len/2] * PW[pos];
	            a[i+j] = v + u;
	            a[i+j+len/2] = v - u;
	            pos += diff;
	            if (pos >= LEN) pos -= LEN;
	        }
	    }
	}
	if (invert)
	    FOR (i, 0, SZ(a))
	        a[i] /= SZ(a);
}
void initFFT()
{
	double angle = 2 * PI / LEN;
	FOR (i, 0, LEN)
	{
	    double ca = angle * i;
	    PW[i] = base(cos(ca), sin(ca));
	}
}

VI mult(VI A, VI B) {
	int L = 1;
	int K = 30000;
	while (L <= SZ(A) + SZ(B)) L *= 2;
	L *= 2;
	vector<base> A1(L), A2(L), B1(L), B2(L);
	FOR(i,0,SZ(A))
	{
	    A1[i] = A[i] / K;
	    A2[i] = A[i] % K;
	}
	FOR(i,0,SZ(B))
	{
	    B1[i] = B[i] / K;
	    B2[i] = B[i] % K;
	}

	fft(A1, 0);
	fft(A2, 0);
	fft(B1, 0);
	fft(B2, 0);
	vector<base> C1(L), C2(L), C3(L);
	FOR(i,0,L)
	{
	    C1[i] = A1[i] * B1[i];
	    C2[i] = A2[i] * B1[i] + A1[i] * B2[i];
	    C3[i] = A2[i] * B2[i];
	}
	fft(C1, 1);
	fft(C2, 1);
	fft(C3, 1);

	vector<int> res(SZ(A) + SZ(B) - 1);
	FOR(i,0,SZ(res))
	{
	    res[i] = ((Int)(C1[i].real() + 0.5) % MOD * K * K % MOD + (Int)(C2[i].real() + 0.5) % MOD * K + (Int)(C3[i].real() + 0.5)) % MOD;
	}
	return res;
}

VI add(VI A, VI B) {
	VI C(max(SZ(A), SZ(B)));
	FOR(i,0,SZ(A))
	    C[i] += A[i];
	FOR(i,0,SZ(B))
	{
	    C[i] += B[i];
	    if (C[i] >= MOD) C[i] -= MOD;
	}
	return C;
}

char buf[MAX];

int main(int argc, char* argv[])
{
	// freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	initFFT();

	F[0] = 1;
	FOR(i,1,MAX)
	    F[i] = F[i - 1] * i % MOD;

	FOR(i,0,MAX)
	{
	    IF[i] = bpow(F[i], MOD - 2);
	}  

	pw2[0] = 1;
	FOR(i,1,MAX)
	    pw2[i] = pw2[i - 1] * 2 % MOD; 

	int t;
	cin >> t;
	FOR(tt,0,t)
	{
	    map<Int, PII> M;
	    map<Int, int> P;

	    int n , m , h;
	    cin >> n >> m;
	    // cin >> h;
	    FOR(i,0,n)
	    {
	        scanf("%s", buf);
	        string s = buf;
	        Int hs = 0;
	        Int hr = 0;
	        FOR(i,0,SZ(s))
	        {
	            hs = hs * 1000003 + s[i];
	            hr = hr * 1000003 + s[SZ(s) - i - 1];
	        }
	        if (hs == hr)
	        {
	            P[hs] ++;
	        }
	        else
	        {
	            if (hs < hr)
	            {
	                M[hs].first ++;
	            }
	            else
	            {
	                M[hr].second ++;
	            }
	        }
	    }

	    vector<VI> A;
	    vector<pair<VI, VI> > B;
	    for(auto it = M.begin(); it != M.end(); ++it)
	    {
	        auto p = it->second;

	        VI X;
	        FOR(j,0,min(p.first, p.second) + 1){
	            int coef = C(p.first, j) * C(p.second, j) % MOD * F[j] % MOD * pw2[j] % MOD;
	            X.push_back(coef);
	        }
	        A.push_back(X);
	    }
	    for(auto it = P.begin(); it != P.end(); ++it)
	    {
	        int x = it->second;
	        
	        VI X, Y;
	        FOR(j,0,x + 1)
	        {
	            Int coef = 1;
	            if (j % 2 == 1)
	                coef = x;
	            coef *= C(x - j % 2, j / 2) * C(x - j % 2 - j / 2, j / 2) % MOD * F[j / 2] % MOD;
	            coef %= MOD;
	            
	            if (j % 2 == 0)
	            {
	                X.push_back(coef);
	            }
	            else
	            {
	                Y.push_back(coef);
	            }
	        }
	        B.push_back(MP(X, Y));
	        
	    }
	    
	    set<PII> S;
	    FOR(i,0,SZ(A))
	    {
	        S.insert(MP(SZ(A[i]), i));
	    }
	    while (SZ(S) > 1)
	    {
	        auto p = *S.begin();
	        S.erase(S.begin());
	        auto q = *S.begin();
	        S.erase(S.begin());
	        int x = p.second;
	        int y = q.second;
	        A[x] = mult(A[x], A[y]);
	        {
	            VI tmp;
	            A[y].swap(tmp);
	        }
	        S.insert(MP(SZ(A[x]), x));
	    }
	    VI R;
	    if (SZ(S) == 1)
	        R = A[S.begin()->second];
	    else
	        R = VI(1, 1);
	    
	    S.clear();
	    FOR(i,0,SZ(B))
	    {
	        S.insert(MP(SZ(B[i].first) + SZ(B[i].second), i));
	    }
	    while(SZ(S) > 1)
	    {
	        auto p = *S.begin();
	        S.erase(S.begin());
	        auto q = *S.begin();
	        S.erase(S.begin());
	        int x = p.second;
	        int y = q.second;
	        B[x].second = add(mult(B[x].second, B[y].first), mult(B[x].first, B[y].second));
	        B[x].first = mult(B[x].first, B[y].first);
	        {
	            VI tmp1, tmp2;
	            B[y].first.swap(tmp1);
	            B[y].second.swap(tmp2);
	        }
	        S.insert(MP(SZ(B[x].first) + SZ(B[x].second), x));
	    }

	    VI T(1, 0);
	    if (SZ(S) == 1)
	    {
	        T = mult(R, B[S.begin()->second].second);
	        R = mult(R, B[S.begin()->second].first);
	    }

	    Int res = 0;
	    FOR(i,1,SZ(R))
	    {
	        if (2 * i > m) break;
	        res += (Int)R[i] * F[i];
	        res %= MOD;
	    }
	    FOR(i,0,SZ(T))
	    {
	        if (2 * i + 1 > m) break;
	        res += (Int)T[i] * F[i];
	        res %= MOD;
	    }
	    cout << res << endl;

	}  

	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

	
}

Tester's Solution

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 400007;

const int MOD = 1000000007;

const double Pi = acos(-1.0);

Int F[MAX];
Int IF[MAX];

Int bpow(Int a, Int k)
{
	Int res = 1;
	while (k) {
	    if (k & 1) {
	        res *= a;
	        res %= MOD;
	    }
	    a *= a;
	    a %= MOD;
	    k /= 2;
	}
	return res;
}

Int C(int n, int k)
{
	return F[n] * IF[k] % MOD * IF[n - k] % MOD;
}

Int pw2[MAX];

typedef complex<double> base;
const int LEN = 1<<17; // max length, power of 2
base PW[LEN]; // LEN-th roots of -1
void fft(vector<base>& a, bool invert)
{
	int lg = 0;
	while((1<<lg) < SZ(a)) lg++;
	FOR (i, 0, SZ(a))
	{
	    int x=0;
	    FOR (j, 0, lg)
	        x |= ((i>>j)&1)<<(lg-j-1);
	    if(i<x)
	        swap(a[i], a[x]);
	}
	for (int len = 2; len <= SZ(a); len *= 2)
	{
	    int diff = LEN / len;
	    if (invert) diff = LEN - diff;
	    for (int i = 0; i < SZ(a); i += len)
	    {
	        int pos = 0;
	        FOR (j, 0, len/2)
	        {
	            base v = a[i+j];
	            base u = a[i+j+len/2] * PW[pos];
	            a[i+j] = v + u;
	            a[i+j+len/2] = v - u;
	            pos += diff;
	            if (pos >= LEN) pos -= LEN;
	        }
	    }
	}
	if (invert)
	    FOR (i, 0, SZ(a))
	        a[i] /= SZ(a);
}
void initFFT()
{
	double angle = 2 * PI / LEN;
	FOR (i, 0, LEN)
	{
	    double ca = angle * i;
	    PW[i] = base(cos(ca), sin(ca));
	}
}

VI mult(VI A, VI B) {
	int L = 1;
	int K = 30000;
	while (L <= SZ(A) + SZ(B)) L *= 2;
	L *= 2;
	vector<base> A1(L), A2(L), B1(L), B2(L);
	FOR(i,0,SZ(A))
	{
	    A1[i] = A[i] / K;
	    A2[i] = A[i] % K;
	}
	FOR(i,0,SZ(B))
	{
	    B1[i] = B[i] / K;
	    B2[i] = B[i] % K;
	}

	fft(A1, 0);
	fft(A2, 0);
	fft(B1, 0);
	fft(B2, 0);
	vector<base> C1(L), C2(L), C3(L);
	FOR(i,0,L)
	{
	    C1[i] = A1[i] * B1[i];
	    C2[i] = A2[i] * B1[i] + A1[i] * B2[i];
	    C3[i] = A2[i] * B2[i];
	}
	fft(C1, 1);
	fft(C2, 1);
	fft(C3, 1);

	vector<int> res(SZ(A) + SZ(B) - 1);
	FOR(i,0,SZ(res))
	{
	    res[i] = ((Int)(C1[i].real() + 0.5) % MOD * K * K % MOD + (Int)(C2[i].real() + 0.5) % MOD * K + (Int)(C3[i].real() + 0.5)) % MOD;
	}
	return res;
}

VI add(VI A, VI B) {
	VI C(max(SZ(A), SZ(B)));
	FOR(i,0,SZ(A))
	    C[i] += A[i];
	FOR(i,0,SZ(B))
	{
	    C[i] += B[i];
	    if (C[i] >= MOD) C[i] -= MOD;
	}
	return C;
}

char buf[MAX];

int main(int argc, char* argv[])
{
	// freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	initFFT();

	F[0] = 1;
	FOR(i,1,MAX)
	    F[i] = F[i - 1] * i % MOD;

	FOR(i,0,MAX)
	{
	    IF[i] = bpow(F[i], MOD - 2);
	}  

	pw2[0] = 1;
	FOR(i,1,MAX)
	    pw2[i] = pw2[i - 1] * 2 % MOD; 

	int t;
	cin >> t;
	FOR(tt,0,t)
	{
	    map<Int, PII> M;
	    map<Int, int> P;

	    int n , m , h;
	    cin >> n >> m;
	    //cin >> h;
	    FOR(i,0,n)
	    {
	        scanf("%s", buf);
	        string s = buf;
	        Int hs = 0;
	        Int hr = 0;
	        FOR(i,0,SZ(s))
	        {
	            hs = hs * 1000003 + s[i];
	            hr = hr * 1000003 + s[SZ(s) - i - 1];
	        }
	        if (hs == hr)
	        {
	            P[hs] ++;
	        }
	        else
	        {
	            if (hs < hr)
	            {
	                M[hs].first ++;
	            }
	            else
	            {
	                M[hr].second ++;
	            }
	        }
	    }

	    vector<VI> A;
	    vector<pair<VI, VI> > B;
	    for(auto it = M.begin(); it != M.end(); ++it)
	    {
	        auto p = it->second;

	        VI X;
	        FOR(j,0,min(p.first, p.second) + 1){
	            int coef = C(p.first, j) * C(p.second, j) % MOD * F[j] % MOD * pw2[j] % MOD;
	            X.push_back(coef);
	        }
	        A.push_back(X);
	    }
	    for(auto it = P.begin(); it != P.end(); ++it)
	    {
	        int x = it->second;
	        
	        VI X, Y;
	        FOR(j,0,x + 1)
	        {
	            Int coef = 1;
	            if (j % 2 == 1)
	                coef = x;
	            coef *= C(x - j % 2, j / 2) * C(x - j % 2 - j / 2, j / 2) % MOD * F[j / 2] % MOD;
	            coef %= MOD;
	            
	            if (j % 2 == 0)
	            {
	                X.push_back(coef);
	            }
	            else
	            {
	                Y.push_back(coef);
	            }
	        }
	        B.push_back(MP(X, Y));
	        
	    }
	    
	    set<PII> S;
	    FOR(i,0,SZ(A))
	    {
	        S.insert(MP(SZ(A[i]), i));
	    }
	    while (SZ(S) > 1)
	    {
	        auto p = *S.begin();
	        S.erase(S.begin());
	        auto q = *S.begin();
	        S.erase(S.begin());
	        int x = p.second;
	        int y = q.second;
	        A[x] = mult(A[x], A[y]);
	        {
	            VI tmp;
	            A[y].swap(tmp);
	        }
	        S.insert(MP(SZ(A[x]), x));
	    }
	    VI R;
	    if (SZ(S) == 1)
	        R = A[S.begin()->second];
	    else
	        R = VI(1, 1);
	    
	    S.clear();
	    FOR(i,0,SZ(B))
	    {
	        S.insert(MP(SZ(B[i].first) + SZ(B[i].second), i));
	    }
	    while(SZ(S) > 1)
	    {
	        auto p = *S.begin();
	        S.erase(S.begin());
	        auto q = *S.begin();
	        S.erase(S.begin());
	        int x = p.second;
	        int y = q.second;
	        B[x].second = add(mult(B[x].second, B[y].first), mult(B[x].first, B[y].second));
	        B[x].first = mult(B[x].first, B[y].first);
	        {
	            VI tmp1, tmp2;
	            B[y].first.swap(tmp1);
	            B[y].second.swap(tmp2);
	        }
	        S.insert(MP(SZ(B[x].first) + SZ(B[x].second), x));
	    }

	    VI T(1, 0);
	    if (SZ(S) == 1)
	    {
	        T = mult(R, B[S.begin()->second].second);
	        R = mult(R, B[S.begin()->second].first);
	    }

	    Int res = 0;
	    FOR(i,1,SZ(R))
	    {
	        if (2 * i > m) break;
	        res += (Int)R[i] * F[i];
	        res %= MOD;
	    }
	    FOR(i,0,SZ(T))
	    {
	        if (2 * i + 1 > m) break;
	        res += (Int)T[i] * F[i];
	        res %= MOD;
	    }
	    cout << res << endl;

	}  

	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

	
}

Feel free to share your approach, if you want to. (even if its same ) . Suggestions are welcomed as always had been.

utkarsh911 · October 6, 2019, 10:07pm

Didn’t understand the exclusion of the factor (2^j) in case of palindromic groups.

In the problem statement, it is written that we need to provide pairwise distinct order of indices (and not pairwise distinct order of strings). So, a string str present at index i and j when passed to the machine is passed as (i,j) and not (str,str). Here (i,j) can be written as (j,i) and hence 2^j should be here.

Where am I going wrong?

taran_1407 · October 7, 2019, 3:56pm

In non-palindrome groups, we were selecting j items each from two different sets of size x and y and then making pairs. So, when we select j elements from first group and j elements from second group, we didn’t consider their order.

But in case of palindromic group, we first select left j elements, and then right j elements from the same group, so an element being selected on left group vs right group is already considered.

utkarsh911 · October 7, 2019, 4:04pm

I guess the 2nd point of the “Not so quick explanation” got trimmed out because of the editor.

" Let’s define two types of groups, palindrome group, which stores frequency of the string, and"

taran_1407 · October 7, 2019, 4:42pm

Yes. It was a typo.
Updated now.