Palindromaniac

Ads

 
 

Share on Google+Share on Google+

Prerak Mall
Palindromaniac
1 Answer(s)      5 years and 2 months ago
Posted in : Java Beginners

Ever wondered about strings full of palindromes? The strange folks in the magical world of mamamam speak in such strings.

You might have noticed that every sub-string of length three in "mamamam" is a palindrome.

You have been given a task by the half-lion half-goat king of mamamam who wants to devise a language for mamamam.

You are to find the number of strings with length N such that every sub-string of length K of such a string is a palindrome. Furthermore these strings are restricted to an alphabet containing only M symbols.

Since this number can be very large, output it modulo 1000000007, the king's favourite prime number. Input A single line containing the integers N, M and K Output A single line containing the number required.

Sample Inputs

Input: 3 2 2

Output: 2

Input: 4 3 2

Output: 3

Ads
View Answers

March 4, 2012 at 7:10 AM


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

long long int modular_pow(long long int base,long long int exponent, long long int modulus) ;

int main()
{
long long int i,j,m,n,k,z,ans;
scanf("%lld%lld%lld",&n,&m,&k);

z=k-(k/2)*2;
if(z==0){
  ans =  modular_pow(m,k/2,1000000007);
  }

else {
  ans =  modular_pow(m,(k+1)/2,1000000007);
}

printf("%lld\n",ans); 

return 0 ;
} 


long long int modular_pow(long long int base,long long int exponent, long long int modulus)
{
   long long int result = 1 ;
    while (exponent > 0) {
        if ((exponent & 1) == 1) {
           result = (result * base) - ((result * base)/modulus)*modulus ;}
        exponent = exponent >> 1 ;
        base = (base * base) - ((base * base)/modulus)*modulus ;
       }
    return result ;
}

Ads









Related Tutorials/Questions & Answers:
Tutorials   
Java Spring Hibernate Struts Training What type of programming language is Java? How do beginners learn about Java? ClassNotFoundException HttpRequestInterceptor java.lang.noclassdeffounderror: org/apache/http/httprequest noclassdeffounderror: org/apache/http/client/methods/httpurirequest java.lang.NoClassDefFoundError: org/apache/http/client/HttpClient How do I resolve this Java Class not found exception? httpclient java.lang.NoClassDefFoundError Apache Commons ioutils maven dependency Read/Convert an inputStream to a String What is the meaning of Java Platform? Why Java is a platform independent language? What is the benefits of learning Core Java? Which technology should I learn after Java? What is array in java with example? How to Convert ArrayList to Array? How to substring in Java? How to format number in Java? What is instance variable in Java? How to download MySQL JDBC driver? What is Calendar class in Java? Which is the best Java tutorials for beginners? How to rename a file in Java? How to delete file in Java code? How to get day from date in Java using Calendar? How to get day of week in Java? How to calculate Date Difference in Java? How to compare date in Java? How to declare array in Java? How to calculate average of array in Java? What is Array in Java? write a java program to find the summation of all the integers entered on command line Sum of two numbers using command line arguments in Java How to create and use Array in Java? How to pass command line arguments in Java? How to create Applet Hello World? Appending String efficiently in Java How to append String in Java? How to list even numbers between 1 and 100? How to add BigDecimal in Java? What is Abstraction In Java? Which is best Beginners Java Tutorial? What is java.util package? Create list from array in Java Filter collection in Java 8 What is the best way to filter a Java Collection? Easy way to transform Collection to Array? How to convert Collection to Array in Java? What are Basic Java Language Elements? Advanced Java Tutorials in 2017

Ads

 
Advertisement null

Ads