What's the matter with modulo? :)

Hi,

I solved the TAPALIN problem easily using memoisation for remembering already calculated results, but when I try the program for results larger than modulo that’s when the problems start. You see, whenever there’s modulo involved I get WA, because I overlook some modulo - characteristic issues. Here I give you my code with modulo operations included, and I kindly ask anyone who is willing to help me to tell me exactly how I can display my results with modulo and in general, how to work with modules. I think it will be helpful for many people.

#include <stdio.h>

#define MAX_N 1000000000
#define MODULO 1000000007

    unsigned long long memo[MAX_N/100];
        //I know I could use O(log n) power function but the main goal was practicing memoisation
        unsigned long palindromes_count(unsigned long N)
        {
        	if (N<1)
        		return 0;
        	else
        	{
        		if (memo[N])
        			return (memo[N] + (palindromes_count(N-1)%MODULO));
        		else
        			{
        				unsigned i;
        				unsigned long temp = 1;
        				if (N%2 == 0)
        				{
        					for(i=0;i<N/2;i++)
        						temp = (temp*26)%MODULO;
        					memo[N] = temp;
        					memo[N-1] = temp;
        					return (memo[N] + (palindromes_count(N-1)%MODULO))%MODULO;
        				}
        				else
        				{
        					for(i=0;i<N/2 + 1;i++)
        						temp = (temp*26)%MODULO;
        					memo[N] = temp;
        					memo[N+1] = temp;
        					return (memo[N] + palindromes_count(N-1)%MODULO)%MODULO;
        				}
        			}
        	}
        }
        
        int main()
        {
        	unsigned T,i;
        	unsigned long N, sum = 0;
        	scanf("%u",&T);
        	
        	for(i=0; i<T; i++)
        	{
        		scanf("%lu",&N);
        		printf("%lu\n",palindromes_count(N));
        	}
        	
        	system("PAUSE");
        	return 0;
        }

Kindest regards,

Petar Vukmirovic.

1 Like

Simple conversion rules:

a+b -> (a+b)%MOD

ab -> (ab)%MOD

a/b -> (a*invmodulo(b))%MOD

So something like memo[N] + (palindromes_count(N-1)%MODULO)

should become (memo[N] + palindromes_count(N-1))%MODULO

Also use long long instead of long (since long is the same as int on most compilers). Use %l64d for printing and scaning them

To simplify the conversions further:

(a*b)%c = ((a%c) * (b%c)) % c
(a+b)%c = ((a%c) + (b%c)) % c

We do this to ensure that in each step we do not overflow the results and we keep the required variable’s value below the given number to which mod is required.

Thanks, that was helpful :slight_smile:

//