問題描述
小易擁有一個擁有魔力的手環(huán)上面有n個數(shù)字(構(gòu)成一個環(huán)),當這個魔力手環(huán)每次使用魔力的時候就會發(fā)生一種奇特的變化：每個數(shù)字會變成自己跟后面一個數(shù)字的和(最后一個數(shù)字的后面一個數(shù)字是第一個),一旦某個位置的數(shù)字大于等于100就馬上對100取模(比如某個位置變?yōu)?03,就會自動變?yōu)?).現(xiàn)在給出這個魔力手環(huán)的構(gòu)成澳腹，請你計算出使用k次魔力之后魔力手環(huán)的狀態(tài)。
輸入描述
輸入數(shù)據(jù)包括兩行：
第一行為兩個整數(shù)n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行為魔力手環(huán)初始的n個數(shù)杨何，以空格分隔酱塔。范圍都在0至99.
輸出描述
輸出魔力手環(huán)使用k次之后的狀態(tài)，以空格分隔晚吞，行末無空格延旧。
輸入例子
3 2
1 2 3
輸出例子
8 9 7
分析
可以構(gòu)造一個n*n的矩陣M。把當前狀態(tài)看成一個向量槽地，那么下一個狀態(tài)向量就是當前向量乘以矩陣的結(jié)果迁沫。假設(shè)初始狀態(tài)列向量(n*1)為v，那么最終的狀態(tài)向量等于M*M*...M*v = M^k * v（k為狀態(tài)變換的次數(shù)）.于是問題轉(zhuǎn)換為如何快速求解矩陣的冪捌蚊。我們可以用二分法快速求解矩陣的冪集畅，計算復雜度為logn。
note
- 矩陣可以方便地描述向量數(shù)據(jù)的變化
- 二分法可以把問題的復雜度將至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;
}
