401571: GYM100495 C I need some help!

Hello, guys,

Could you help me to improve my program? I already posted this question on several online judges, but nobody answered. So I hope to receive an answer from you. Sorry for posting this directly to the problemset (not to my blog) :)

I don't remember the exact problem statement. But the input is 10 positive integers and I think that my program is correct. I get TLE (time limit exceeded). It might be ineffective but I don't know why.

Here is my program:

#include <cstdio>
using namespace std;

typedef long long ll;

const int mod = 1000000007;
const int Maxn = 10;

int a[Maxn];
int x;

int Tribonacci(int x) 
{
        if (x == 0) return 0;
        if (x <= 2) return 1;
        return Tribonacci(x - 3) + Tribonacci(x - 2) + Tribonacci(x - 1);
}

int Fibonacci(int x)
{
        if (x == 0) return 0;
        if (x == 1) return 1;
        return Fibonacci(x - 2) + Fibonacci(x - 1);
}

int toPower(int x, int p)
{
        int res = 1;
        for (int i = 0; i < p; i++)
                res = ll(res) * x % mod;
        return res;
}

int friendlyFibonacciFunction(int x)
{
        return toPower(Fibonacci(x + 25), Tribonacci(x + 20));
}

int myFunction(int x)
{
        if (x < Maxn) return a[x];
        int sum = 0, res = 0;
        for (int i = 1; i <= Maxn; i++) {
                sum = (sum + myFunction(x - i)) % mod;
                res = (res + ll(friendlyFibonacciFunction(i)) * sum % mod) % mod;
        }
        return res;
}

int main()
{
        for (int i = 0; i < Maxn; i++)
                scanf("%d", &a[i]);
        scanf("%d", &x);
        printf("%d", myFunction(x));
        return 0;
}

Could you submit your correct program which solves the problem correctly and effectively?

The first line contains the number of test cases T (1 ≤ T ≤ 10⁴).

In the first line of every test case there are 11 integers a₀, a₁, ..., a₉ (1 ≤ a_i ≤ 10⁹) and x (0 ≤ x ≤ 2·10⁹).

For each test case output one line containing “Case #tc: answer” where tc is the number of the test case (starting from 1) and answer is the result of myFunction(x).

2
1 2 3 4 5 6 7 8 9 10 10
1 2 3 4 5 6 7 8 9 9 9

Case #1: 853943371
Case #2: 9