HDU 5170/5171：大数比较取对数 / 斐波那契矩阵加速贪心

HDU 5170：大整数幂比较

比较 a^b 与 c^d 大小。直接算溢出，取对数：b·log10(a) vs d·log10(c)。注意精度，设阈值 1e-9。

while (cin >> a >> b >> c >> d) {
    double x = b * log10(a), y = d * log10(c);
    if (x - y > 1e-9) puts(">");
    else if (y - x > 1e-9) puts("<");
    else puts("=");
}

HDU 5171：贪心 + 斐波那契矩阵快速幂

操作：取两数 a,b 置入 a+b，重复 k 次。最大化最终数组和。贪心：每次取最大、次大。设最大为 a1，次大为 b1。
第 1 次加入 a1+b1
第 2 次加入 2a1+b1
第 3 次加入 3a1+2b1
第 4 次加入 5a1+3b1
系数为斐波那契数列。用 3×3 矩阵快速幂求前 k 项系数和。

矩阵构造

状态向量 [F_{i}, F_{i-1}, S_i]^T，其中 S_i = Σ_{j=1}^i F_j。
转移矩阵： ``` [1 1 0] [1 0 0] [1 1 1] ``` M^k 作用于初始向量得 S_k。

C++ 实现

const int MOD = 1e7+7;
struct Matrix { long long f[4][4]; };
Matrix mul(Matrix a, Matrix b) { /* 标准矩阵乘法 */ }
Matrix qpow(Matrix a, int n) { /* 快速幂 */ }

int main() {
    int n, k;
    Matrix M = {{{1,1,0},{1,0,0},{1,1,1}}};
    while (cin >> n >> k) {
        vector a(n+1);
        long long sum = 0;
        for (int i = 1; i <= n; ++i) { cin >> a[i]; sum = (sum + a[i]) % MOD; }
        sort(a.begin()+1, a.end());
        int a1 = a[n], b1 = a[n-1];
        Matrix T = qpow(M, k);
        long long c1 = (T.f[2][0] + T.f[2][1]*0 + T.f[2][2]*0) % MOD; // F_k 系数
        T = qpow(M, k-1);
        long long c2 = (T.f[2][0] + T.f[2][1]*0 + T.f[2][2]*0) % MOD; // F_{k-1} 系数
        sum = (sum + c1*a1 + (c2+1)*b1) % MOD;
        cout << sum << endl;
    }
}

关键点

1. 对数比较：避免大数溢出，精度阈值处理相等判断
2. 贪心正确性：每次合并最大两数使增量最大
3. 斐波那契矩阵：3×3 矩阵同时得到项值与前缀和