What's the matter with modulo? :)

general
,
1

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.

2

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

3

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.

4

Thanks, that was helpful :slight_smile: