拼多多算法笔试-第4题

第一题：排序后，取前 2*m 个数字，依次头尾组合即可。理由：假设 a b c d 升序排列，那么 a*d + b*c 是最小的乘积和，因为只要任意改变一下组合方式，比如改成 a*c + b*d，则 (a*c + b*d) - (a*d + b*c) = (b-a)*(d-c) > 0，会变大。

第二题：中午刚学了线段树，不太熟悉，不会写。

第三题：不会。

第四题：幸好有之前写过矩阵快速幂的题，吭哧吭哧折腾了一个半小时才AC，搞的最后第二题都没时间写个暴力版，唉。。。

主要思路是：N 天被 M 个点切割成 M+1 段，每段连续的时间使用矩阵快速幂递推。

以下是第四题AC代码：

#include <iostream>
#include <vector>
#include <cstring>
#define LL long long
using namespace std;

const int sz = 4, MOD = 1000000007;  // sz 为 矩阵维数
//注意：此矩阵以下标1开始作为逻辑上的第一个数，而不是0
struct Matrix {
  LL a[sz+1][sz+1];  //注意，这里必须是long long，否则会溢出，导致结果不正确
  Matrix() { memset(a, 0, sizeof a); }  //初始化为 0
  Matrix operator*(const Matrix &b) const {
    Matrix res;
    LL r;
    for (LL i = 1; i <= sz; ++i)
        for (LL k = 1; k <= sz; ++k) {  //这种写法可以充分利用空间局部性，提升常数级的性能
            r = a[i][k];
            for (LL j = 1; j <= sz; ++j)
                res.a[i][j] = (res.a[i][j] + r * b.a[k][j]) % MOD;
        }
    return res;
  }
} ans, base;

void init_base() {  //初始化矩阵：ans为初始值，base为需要快速幂的矩阵
    base.a[1][1] = base.a[2][2] = base.a[3][3] = base.a[4][4] = 0;
    for (LL i = 0; i <= sz; i++) {
        for (LL j = 0; j <= sz; j++) 
        if (i != j) base.a[i][j] = 1;
        else base.a[i][j] = 0;
    }
}

void init_ans() {
    for (LL i = 0; i <= sz; i++) {
        for (LL j = 0; j <= sz; j++) ans.a[i][j] = 1;
    }
}

void qpow(LL b) {
  while (b) {
    if (b & 1) ans = base * ans;  // 注意base矩阵是左乘还是右乘!!!
    base = base * base;
    b >>= 1;
  }
}

vector<LL> W(1001, 0);
vector<LL> C(1001, 0);

int main() {
    LL T, N, M;
    cin >> T;
    for (LL i = 0; i < T; i++) {
        cin >> N >> M;
        if (M == 0) {
            init_base();
            init_ans();
            qpow(N-1);
            cout << ((ans.a[1][1] + ans.a[2][1] + ans.a[3][1] + ans.a[4][1]) % MOD) << endl;
        } else {
            init_base();
            init_ans();
            for (LL i = 0; i < M; i++) cin >> W[i];
            for (LL i = 0; i < M; i++) cin >> C[i];
            LL start = 1;
            for (LL i = 0; i < M; i++) {
                init_base();
                qpow(W[i] - start);
                if (C[i] == 1) {ans.a[2][1] = ans.a[3][1] = ans.a[4][1] = 0;}
                else if (C[i] == 2) {ans.a[1][1] = ans.a[3][1] = ans.a[4][1] = 0;}
                else if (C[i] == 3) {ans.a[2][1] = ans.a[1][1] = ans.a[4][1] = 0;}
                else {ans.a[2][1] = ans.a[3][1] = ans.a[1][1] = 0;}
                start = W[i];
            }
            init_base();
            qpow(N-start);
            cout << ((ans.a[1][1] + ans.a[2][1] + ans.a[3][1] + ans.a[4][1]) % MOD) << endl;
        }
    }
    return 0;
}

#拼多多##题解#