这是考察的哪种数据结构？

[LuckyPocketWatch]

这周抽时间去了某家公司面试，面试先让做一些题目，其中一条如下

假设 x 的值范围[0,255]，现在有多项式 f(n) = An + Bn * C^x;其中 An 和 Bn 是根据 n 的值而变化，C 为固定值,而 x 的值会根据 n 的值随机选择[0,255]中的一个值。假设有 50 亿个这样的多项式，需要求多项式和，既求 f(0)+f(1)+...+f(50 亿),问：如何通过变化多项式来减少计算次数？

C^x 表示 C 的 x 次方，下同

这题目我直接没写，我不知道如何变化多项式来减少计算次数，笔试完面试的人让我再次看下这条题目，问能不能再想下，我想了一会实在想不出答案，老实回答不知道。然后面试的人表示我对数据结构这块比较欠缺，然后他告诉了我正确答案：

由于 x 的范围是[0,255]，而 C 是一个常量，所以可以构建一个数组，包含 255 个值，对应 C^0,C^1,C^2...C^255 ，这样每次计算 f(n)的值的时候，就不用每次都计算 C^x ，而只需要根据 x 的值，从数组中查找对应的值即可。通过这种方法，原本需要计算 50 亿次的 C^x 的值，现在只需要提前计算 255 次 C^x 的值，然后每次需要的时候去数组中提取即可

我想问下，这条题目是考察的哪种数据结构？

[changnet]

这题目误导人啊。我看了题目，主要是有 50 亿个这样的多项式，要求是通过变化多项式来减少计算次数。

我首先想的是有什么算法可以合并这些式子，一次算出来，类似于奥数的多项式合并。

所以算法应该是如何让这 50 亿次快速算出来，而不是去关注这多项式里的 C^x 如何优化。因为即使优化了这一小部分，还是需要 50 亿的计算。

面试题就应该要突出考查的重点。结果就考了个缓存，50 亿的计算量一个没少，真是考了个寂寞。

[hello2090]

@me1onsoda 既然 50 亿个方程，那肯定要算 50 亿次，但每次的 C^X 只要读出来，不用每次都算了啊

[ccde8259]

答 Cache 掉 C^x 都算对……