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.