A[1] := 0;
A[2] := 1; // this line is wrong, must be A[2] := 1 mod P

test
1 1
answer is 0

thX AC

// JAVA :
import java.io.*;
import java.util.Arrays;
public class Task_1537 {
    public static void main(String[] args) throws Exception{
        StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));
        st.nextToken();
        int k = (int) st.nval;
        st.nextToken();
        int p = (int) st.nval;
        if(k<2)System.out.println(0);
        else {
        int t[] = new int[k+1];
        t[2] = 1 % p;
        for (int i = 3; i <= k; i++){
            if ((i & 1) == 1)
                t[i] = t[i-1];
            else t[i] = t[i-1] + t[i/2];
            if (t[i] >= p)
                t[i] = t[i] - p;
        }
        //System.out.println(Arrays.toString(t));
        System.out.println(t[k]);
       }
    }

}



// C++ :

#include<stdio.h>
int main(){
    int k,p,i;
    int *t;
    scanf("%i%i",&k,&p);
    if(k<2)printf("0");
    else {
    t = new int[k+3];
        t[2] = 1 % p;
        for (i = 3; i <= k; i++){
            if ((i & 1) == 1)
                t[i] = t[i-1];
            else t[i] = t[i-1] + t[i/2];
            if (t[i] >= p)
                t[i] = t[i] - p;
        }
        printf("%i",t[k]);
    }
}

1)50 100
ans:93
2)1000 1000
ans:939
3)10000 987
ans:697
4)20 20
ans:10
5)10000000 1000000000
ans:636184067
I hope it will help you!!!


Edited by author 08.05.2007 19:22

local variables are located in stack, so
if you want to avoid stack overflow(crash)
you can't declare big arrays inside functions

int main()
{
__int64 k,p,i;
__int64 A[MAX];

=>

__int64 A[MAX];

int main()
{
__int64 k,p,i;

Pay attention on this line

a[i]=a[i-1]+a[i/2];

mod P also important espacially if P==1

Yes