Magical Strings |
All submissions for this problem are available.
This question is extremely easy. You just need to find the number of magical strings.
A string is called magical if it satisfies the following conditions.
1) Length of the string must be exactly N.
2) Each character of the string must be a lower case latin letter i.e. in ['a' - 'z'].
2) For each pair (L,R) in input, substring [L,R] of this string must be a palindrome.
1) Length of the string must be exactly N.
2) Each character of the string must be a lower case latin letter i.e. in ['a' - 'z'].
2) For each pair (L,R) in input, substring [L,R] of this string must be a palindrome.
Input
First line contains T, the number of test cases.
For each test case, first line contains two integers, N - length of string and M - number of pairs [L,R].
Next M lines, each contains two integers [L,R].
For each test case, first line contains two integers, N - length of string and M - number of pairs [L,R].
Next M lines, each contains two integers [L,R].
Note : L and R are 1 based indexing of string.
Output
For each test case, print the number of magical strings.
As the answer can be large, print it modulus 1000000007 (1e9 + 7).
As the answer can be large, print it modulus 1000000007 (1e9 + 7).
Constraints
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 2000
- 0 ≤ M ≤ 200000
- 1 ≤ L ≤ R ≤ N
Sample Input:
1
3 2
1 2
2 3
3 2
1 2
2 3
Output:
26
-------------------------------------------------------------------------------editorial--------------------------------------------------------
Prerequisites - Pigeon Hole Principle, Disjoint Set Union
Difficulty : Easy - Medium
Expected Complexity: O(N*N)
Editorial -
Difficulty : Easy - Medium
Expected Complexity: O(N*N)
Editorial -
- Find the mid-point of each range (query) and if there are many queries having the same mid-point then only retain that query whose length is max, i.e (where r - l is maxm)
- This would have reduced the number of queries to 2*N at max, since there are 2*N number of mid-points in a string of length N.
- Now for each query do dsu union of element l with r, (l + 1) with (r - 1), (l + 2) with (r - 2) and so on. We do this because the character which would be put on the index l would be same as the one we put on index r. Extending this logic to all queries we need to maintain dsu. So basically all the elements of one component of dsu should have the same letter on them.
- After processing all the queries, let the number of dsu components be x, then the answer is 26x
Complexity Analysis: O(N * N) because we do an O(N) iteration for each query and total number of queries can be 2N, therefore O(2N*N). Here I have ignored the constant of union-find for simplicity.
note 2*n centers since ith position can be center with string of even length around it or with string of odd length around it
-------------------------------------------------code-------------------------------------------------------------------
#include<iostream>
#include<bits/stdc++.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
long long int rank[100010];
long long int parent[100010];
#define mod 1000000007
long long int find(long long int a)
{
if(parent[a]!=parent[parent[a]])
{
parent[a]=find(parent[a]);
}
return parent[a];
}
long long int merge(long long int a, long long int b)
{
long long int x=find(a);
long long int y=find(b);
if(rank[x]>rank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
long long int t; cin>>t;while(t--)
{
long long int n,q;
cin>>n>>q;
for(long long int i=0;i<=n;i++)
{
rank[i]=1;
parent[i]=i;
}
vector<pair<long long int ,long long int > > v;
long long int haa[10000][2];// 0 for even 1 for odd
memset(haa,0,sizeof haa);
while(q--)
{
long long int l,r;
cin>>l>>r;
if((r-l+1)%2==0)
{
long long int mid=(r+l)/2;
long long int len=(r-l+1);
if(haa[mid][0]<len/2) haa[mid][0]=len/2;
}
else
{
long long int mid=(r+l)/2;
long long int len=(r-l+1);
if(haa[mid][1]<len/2) haa[mid][1]=len/2;
}
}
for(long long int i=1;i<=n;i++)
{
if(haa[i][0]!=0)
{
long long int len=haa[i][0];
long long int fp=i;
long long int sp=i+1;
for(long long int j=0;j<len;j++)
{
merge(fp,sp);
fp--;
sp++;
}
}
if(haa[i][1]!=0)
{
long long int len=haa[i][1];
long long int fp=i-1;
long long int sp=i+1;
for(long long int j=0;j<len;j++)
{
merge(fp,sp);
fp--;
sp++;
}
}
}
long long int c=0;
for(long long int i=1;i<=n;i++)
{
if(parent[i]==i)c++;
}
long long int ans=1;
for(long long int i=0;i<c;i++)
{
ans=(ans*26)%mod;
}
cout<<ans<<endl;
}
return 0;
}
