魔力手环

问题描述

小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。

输入描述

输入数据包括两行：
第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.

输出描述

输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。

输入例子

3 2
1 2 3

输出例子

8 9 7

分析

可以构造一个n*n的矩阵M。把当前状态看成一个向量，那么下一个状态向量就是当前向量乘以矩阵的结果。假设初始状态列向量(n*1)为v，那么最终的状态向量等于M*M*...M*v = M^k * v（k为状态变换的次数）.于是问题转换为如何快速求解矩阵的幂。我们可以用二分法快速求解矩阵的幂，计算复杂度为logn。

note

1. 矩阵可以方便地描述向量数据的变化
2. 二分法可以把问题的复杂度将至logn

代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> mult(const vector<vector<int>> &m, const vector<int> &v)
{
    int n = v.size();
    vector<int> product(n, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            product[i] = (product[i] + m[i][j] * v[j]) % 100;
        }
    }
    return product;
}

vector<vector<int>> mult(const vector<vector<int>> &lhs, const vector<vector<int>> &rhs)
{
    int n = lhs.size();
    vector<vector<int>> product(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                product[i][j] = (product[i][j] + lhs[i][k] * rhs[k][j]) % 100;
            }
        }
    }
    return product;
}

vector<vector<int>> power(const vector<vector<int>> &m, int p)
{
    if (p <= 1)
        return m;

    vector<vector<int>> h = power(m, p / 2);

    if (p % 2 == 0)
        return mult(h, h);
    return mult(m, mult(h, h));
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);

    vector<vector<int>> m(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        m[i][i] = m[i][(i + 1) % n] = 1;
    }

    m = power(m, k);
    vector<int> ret = mult(m, v);

    printf("%d", ret[0]);
    for (int i = 1; i < n; i++)
        printf(" %d", ret[i]);

    return 0;
}