Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Saturday, September 7, 2013
Changing the word problem's solution
Question :
Joey's Computer got a bug. Whenever there is a word, it changes itself such that all the letters at the even position comes to the beginning of the word. For ex: "computer" will become "optrcmue", "who" will change to "hwo" etc. But he found out that there will be some words, that will remain same even after this change, for ex. "aab" will remain "aab". Now, if we use only lower case english letters, Joey wants to know how many "N" letters words are there that remain same after this change. As the answer can be quite large, print in modulo 1000000007.
Joey's Computer got a bug. Whenever there is a word, it changes itself such that all the letters at the even position comes to the beginning of the word. For ex: "computer" will become "optrcmue", "who" will change to "hwo" etc. But he found out that there will be some words, that will remain same even after this change, for ex. "aab" will remain "aab". Now, if we use only lower case english letters, Joey wants to know how many "N" letters words are there that remain same after this change. As the answer can be quite large, print in modulo 1000000007.
Inputs :
The first line will contain "T", the no. of testcases. Each of the next "T" lines will have an integer "N".
The first line will contain "T", the no. of testcases. Each of the next "T" lines will have an integer "N".
Outputs :
For each test case, print the number of "N" letters words that will remain same after this change modulo 1000000007.
For each test case, print the number of "N" letters words that will remain same after this change modulo 1000000007.
Constraints :
1 <= T <= 100, 1 <= N <= 10^5
1 <= T <= 100, 1 <= N <= 10^5
Level : Medium
Solution to the Problem :
#include<stdio.h>
long long int arr[100000];
void per()
{
arr[0]=1;
long long int i;
for(i=1;i<100000;i++)
arr[i]=(arr[i-1]*26)%1000000007;
}
void perform(long long int *x,long long int fn,long long int sn)
{
if(x[sn]==0)
{
x[sn]=fn;
return;
}
if(x[sn]<fn)
{
long long int t=x[sn];
x[sn]=fn;
perform(x,t,fn);
return;
}
if(x[sn]>fn)
{
perform(x,fn,x[sn]);
return;
}
}
long long int count(long long int *x,long long int n)
{
long long int c=0;
long long int i;
for(i=1;i<=n;i++)
{
if(!x[i])
c++;
}
return c;
}
long long int count(long long int n)
{
long long int x[n+1];
long long int i;
for(i=1;i<=n;i++)
{
x[i]=0;
}
for(i=1;i<=n;i++)
{
long long int fn,sn;
if(i&1)
{
fn=i;
sn=i-i/2+n/2;
}
else
{
fn=i/2;
sn=i;
}
perform(x,fn,sn);
}
printf("%lld\n",arr[count(x,n)+n%2]);
}
main()
{
per();
long long int t;
scanf("%lld",&t);
while(t--)
{
long long int n;
scanf("%lld",&n);
count(n);
}
}
