题意分析

$a,b,c,d,e,f,g,h$ 是满足 $0<a,b,c,d,e,f,g,h≤1000$的整数。可以证明，对于任意整数 $i≥0$，都有 $0≤Φ(i)≤1000$。现在，对于给定的整数 $a,b,c,d,e,f,g,h,i（0<a,b,c,d,e,f,g,h,i≤1000）$，我们需要编写一个程序计算并输出 $Φ(i)$。

需要注意的是，直接递归实现上述递推关系可能会导致程序在 $i$较大时无法终止，因此需要采用更高效的算法。

解题思路

直接递归的问题 如果直接按照递推公式递归计算$Φ(i)$，对于较大的$i$（例如 $i=1000$），递归调用的层数会非常多，导致程序运行时间过长甚至栈溢出。因此，直接递归的方法不可行。

动态规划优化 为了高效计算 $Φ(i)$，可以采用动态规划（$Dynamic Programming$, $DP$）的方法。动态规划的核心思想是将子问题的解存储起来，避免重复计算。

具体步骤： 初始化：首先，我们初始化 $Φ(0)$ 到 $Φ(7)$ 的值分别为 $a,b,c,d,e,f,g,h$。 递推计算：对于 $i≥8$，我们通过递推公式计算 $Φ(i)$，并将结果存储在数组中。 取模运算：由于结果需要对 $1000$ 取模，我们在每次计算后都进行取模操作，以确保结果在 $0$ 到 $999$ 之间。 公式表示： 对于$i≥8$，递推公式为：

$Φ(i)=(Φ(i−1)+Φ(i−2)−Φ(i−3)+Φ(i−4)−Φ(i−5)+Φ(i−6)−Φ(i−7)+Φ(i−8))mod1000$

标程

#include <iostream>
#include <math.h>
#include <string.h>

using namespace std;

int a, b, c, d, e, f, g, h, i;
int ans[1001];

int mod(int a, int b) {
    int r;
    for (r = 0; r <= b - 1; r++)
        if ((a - r) % b == 0)
            return r;
}

int solve(int n) {  // 顺推过去
    for (int k = 3; k <= n; k++) {
        if (k % 2 == 1) {
            int t = d * ans[k - 1] + e * ans[k - 2] - f * ans[k - 3];
            ans[k] = mod(t, g);
        }
        else {
            int t = f * ans[k - 1] - d * ans[k - 2] + e * ans[k - 3];
            ans[k] = mod(t, h);
        }
    }
    return 0;  // 函数需要有返回值，这里返回0表示正常结束
}

int solve1(int n) {  // 递归思路
    if (ans[n] > -1) return ans[n];
    else if (n % 2 == 1) {
        int t = d * solve1(n - 1) + e * solve1(n - 2) - f * solve1(n - 3);
        ans[n] = mod(t, g);
        return ans[n];
    }
    else {
        int t = f * solve1(n - 1) - d * solve1(n - 2) + e * solve1(n - 3);
        ans[n] = mod(t, h);
        return ans[n];
    }
}

int main(void) {
    int t;
    cin >> t;
    while (t--) {
        // 手动将ans数组初始化为-1
        for (int j = 0; j < 1001; ++j) {
            ans[j] = -1;
        }
        cin >> a >> b >> c >> d >> e >> f >> g >> h >> i;
        ans[0] = a;
        ans[1] = b;
        ans[2] = c;
        solve1(i);
        cout << ans[i] << endl;
    }
    return 0;
}