要准备找工作了，这几天在看july整理的面试题目，很全很强大。其中有个搜狗校招的笔试题目，觉得很有意思。思考了下，感觉相比给出的方法还有更好的方法。

题目

N个整数（数的大小为0-255）的序列，把它们加密为K个整数（数的大小为0-255）.再将K个整数顺序随机打乱，使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法,且要求K<=15*N. 如果是：

1. N<=16,要求K<=16*N.
2. N<=16,要求K<=10*N.
3. N<=64,要求K<=15*N

第1、2问

因为N条件相同，所以第1问和第2问其实是同一个问题，解决了第2问也就搞定了第1问。

简单方法

原理

应题目要求，加密后的K个整数打乱顺序后还要能恢复原文，那么就需要将原文整数的位置信息也编码进密文。

一种简单的方法就是把密文的8位数分成3段

第1部分编码位置，N<=16的情况需要4位来表示
第2部分编码整数的第几位，000表示第0位，111表示第7位
第3部分编码某一位上的数值，如：0110 101 1表示，第6个数的第5位为1

原文整数范围[0-255]有8位，因此编码1个原文数字需要8个密文整数，即 K<=8N。已经可以满足第1、2问的要求了。

栗子

假设原文第6个整数为77，二进制表示为 01001101，那么可以编码成

0110 111 0
0110 110 1
0110 101 0
0110 100 0
0110 011 1
0110 010 1
0110 001 0
0110 000 1

好一点的方法

原理

这里我想到了一种更好一点的方法，可以使 K<=4N

首先，我们将原文整数写成4进制：x = a₃ * 64 + a₂ * 16 + a₁ * 4 + a₀(也就是将原文整数分为4段，每段2位)，记系数为a_i。由于i属于{0, 1, 2, 3}并且a_i也属于{0, 1, 2, 3}，因此我们考虑用2位编码i，2位编码a_i。于是密文的数字就被分为了这么三段

第1部分依然编码位置
第2部分编码i
第3部分编码a_i

这样只需要4个密文整数就可以编码一个原文整数了，即 K<=4N

栗子

假设原文第6个数字为77，二进制表示为 01001101，那么可以编码成

0110 11 01
0110 10 00
0110 01 11
0110 00 01

第三问

好一点的方法

原理

由于N<=64这样就必须用6位来编码位置，剩下只有2位来编码数值了。

继承第1、2问好一点的方法，我们用剩下的2位编码i，用出现的次数编码 a_i。也就是a_i等于多少对应的密文整数就出现多少次。由于i有4个，a_i<=3，故每一个原文整数最多需要4*3=12个密文整数来编码，也就是 K<=12N

栗子

假设原文第6个数字为77，二进制表示为 01001101，那么可以编码成

000110 11
000110 01
000110 01
000110 01
000110 00

更好一点的方法

原理

假设每1个原文整数最多能使用 n 个密文整数来编码。

对于1个密文数字依然需要6位来编码位置，剩下2位来编码数值信息。2位对应4个状态(00, 01, 10, 11)。n 个密文整数分给4个状态，状态出现的次数可以位0，并且n可以不用完。相当于5个状态分n个整数，最后一个状态表示没有用完的整数。则一共有C(n+4, 4)种组合方式。

我们用1种组合方式编码1个数值，[0-255]共有256个数值。那么要求满足 C(n+4, 4) >= 256。求的当n=7时，C(n+4,4)=330 > 256。故这种编码方式可以使得 K<=7N。状态对应的表格在这里下载

栗子

假设原文第6个数字为77，二进制表示为 01001101，那么可以编码成

000110 10
000110 10
000110 01
000110 01
000110 00
000110 00

题目大意

已知斐波那契数列F1 = 1, F2 = 2, Fi = Fi - 1 + Fi - 2 (i > 2)。定义Ai(k) = Fi × ik (i ≥ 1)，求A1(k) + A2(k) + ... + An(k)对1000000007(10⁹+7)取模的结果。(1 ≤ n ≤ 1017; 1 ≤ k ≤ 40)

题目链接： http://codeforces.com/problemset/problem/392/C

解题报告

算法思路

这类题目基本上都是矩阵快速幂。

分析流程

1. 二项式

首先根据二项式定理

可以得到以下等式

2. 简写

为了方便后续公式的书写，我们做如下定义（简写），记

于是上面的公式可以简写为如下形式：

3. 矩阵构造

根据题目意思，令

同时定义一个 k乘1的列向量，该列向量前k－1行均为0，最后一行为1，记为Ik

构造如下矩阵，根据前面简写、定义，可知如下等式成立。

根据上述等式，很容易写出如下的通项公式

4. 初值

根据题目意思，斐波那契数列初值F1 = 1, F2 = 2，可以推断F0 = 1，于是通项公式的初值如下：

5. 求解

部分由矩阵快速幂求解。时间复杂度为O((2k + 3)³ log n)=O(k³ log n)。矩阵快速幂后乘以初值即可得到答案。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long LL;

#define maxn 84
#define MOD 1000000007

LL A[maxn][maxn], C[41][41], ans[maxn][maxn], tp[maxn][maxn];

void gen(int k) {
    for (int i = 0; i <= k; ++i) {
        C[i][0] = C[i][i] = 1;
    }
    for (int i = 2; i <= k; ++i) {
        for (int j = 1; j < i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
    for (int i = 0; i <= k; ++i) {
        for (int j = i; j <= k; ++j) {
            A[i + k + 1][j] = A[i][j + k + 1] = A[i + k + 1][j + k + 1] = C[j][i];
        }
    }
    A[2 * k + 1][2 * k + 2] = 1;
    A[2 * k + 2][2 * k + 2] = 1;
    
    for (int i = 0; i < 2 * k + 3; ++i) {
        ans[i][i] = 1;
    }
}

void multi(LL C[][maxn], LL A[][maxn], LL B[][maxn], int n) {
    memset(tp, 0, sizeof(tp));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                tp[i][j] = (tp[i][j] + A[i][k] * B[k][j] % MOD) % MOD;
            }
        }
    }
    memcpy(C, tp, sizeof(tp));
}

LL solve(LL n, int k) {
    gen(k);
    
    while (n) {
        if (n % 2) {
            multi(ans, A, ans, 2 * k + 3);
        }
        multi(A, A, A, 2 * k + 3);
        n /= 2;
    }
    
    LL res = 0;
    for (int i = 0; i < 2 * k + 2; ++i) {
        res = (res + ans[i][2 * k + 2]) % MOD;
    }
    return res;
}

int main() {
    LL n;
    int k;
    cin >> n >> k;
    
    cout << solve(n, k) << endl;
    

    return 0;
}