SPOJ Problem ORDSUM23

SUMS OF 2 AND 3

Explanation:

This problem requires you to find out number of ways in which a number 'n' can be written as a sum of 2 and 3, and the easy part is you want all the ways, irrespective of the order of the numbers.

This can be easily done using recursion. For a given 'n', number of ways will become, ways(n) = ways(n-2) + ways(n-3). And, so on.

This can be then converted into a classic DP problem.

Below is the code for reference.

Solution:

#include<iostream>
#include<cstdio>
#define SIZE 1000001
#define LLD long long int
#define MOD 1000000007

int main(){
    LLD arr[SIZE];
    arr[0] = arr[1] = 0;
    arr[2] = arr[3] = 1;
    for(int i=4;i<SIZE;i++){
        arr[i] = (arr[i-2] + arr[i-3]) % MOD;
    }
    int t, a;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &a);
        printf("%lld\n", arr[a]);
    }
    return 0;
}

Any suggestions are welcome.