题目大意：查看相关场次即可看到。 思路：推公式的题目，可以用快速幂加公式快速解决，也可以用二进制拆分运算的方法加快速度。 需要注意的一点在于：今后在mod之后有涉及到运算的都要加上一个mod之后再mod，，或者统一都加一个mod 顺便复习一下二进制拆分的方法！！ 二进制拆分的做法AC代码：
using namespace std;long long f[1200000];int a[100010];#define mod 10000007int main(){f[0] = 0;f[1] = 1;f[2] = 2;f[3] = 4;f[4] = 3;f[5] = 5;;for (int i = 6; i < 1200000; i++){f[i] = (f[i – 1] + f[i – 2]+mod) % mod;f[i – 2] = (f[i – 3] + f[i – 2] + mod) % mod;}int n, m;= 0;while (cin >> n >> m){sum = 0;for (int i = 0; i < n; i++){scanf(“%d”, &a[i]);sum += a[i];sum %= mod;}sort(a, a + n);long long b = a[n – 2], c = a[n – 1];int k = 1;int mid = 1;while (m){k = 1;long long bb = b, cc = c;while (k <= m){if (k>(1<<20))break;mid = k;sum = (sum + (f[k] * b + (f[k + 1] – 1)*c + mod) % mod) % mod;bb = b; cc = c;/*f[k]-f[k-1]会出现负的情况，加上一个mod就可以解决！*/c = ((((f[k] – f[k – 1] + mod)%mod)*bb) % mod + (((f[k + 1] – f[k] + mod))%mod*cc) % mod + mod) % mod;b = ((((f[k – 1] – f[k – 2] + mod) % mod)*bb) % mod + (((f[k] – f[k – 1] + mod)%mod)*cc) % mod) % mod;m -= k;k <<= 1;}}cout << sum << endl;}};
快速幂做法晚些奉上！
只有流过血的手指才能弹出世间的绝唱。
