401571: GYM100495 C I need some help!

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. I need some help!time limit per test5.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

In the first line of every test case there are 11 integers a0, a1, ..., a9 (1 ≤ ai ≤ 109) and x (0 ≤ x ≤ 2·109).

Output

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).

ExamplesInput
2
1 2 3 4 5 6 7 8 9 10 10
1 2 3 4 5 6 7 8 9 9 9
Output
Case #1: 853943371
Case #2: 9

加入题单

上一题 下一题 算法标签: