题目描述
tabris实在是太菜了,没打败恶龙,在绿岛也只捡到一块生铁回去了,为了不在继续拉低acimo星球的平均水平逃离地球,来到了Sabi星球.
在这里tabris发现了一种神奇的生物,这种生物不需要与外界交流,种群间不同个体能互相维持生命存在及提供生长所需的能量.
每个种群有N个不同个体,围成一个圈,每隔一个单位时间都会生长.
在一个单位时间里,每个个体会向两边辐射能量,辐射范围与强度均为K,随着距离的增加辐射强度会减小,距离每增加1辐射强度减小1 ,在这单位时间通过辐射接受的能量会保留,最开始的能量会消耗掉。
对于两个个体a、b,其中a对b的辐射会使b增加【辐射强度×a最开始的能量值】.
总体的改变可以表示成
注：[∗] * 为真时为1 *为假时为0
现在tabris想知道经过M单位时间后,每个个体的能量值是多少.
输入描述:
输入一个T,表示测试数据的组数
每个测试数据第一行包含三个正整数N,M,K.
接下来一行包含N个正整数a[i];
T∈[1,200]
N∈[1,200]
K∈[1,⌊n/2⌋]
M∈[1,1018]
a[i]∈[1,106]
输出描述:
对每组测试样例输出经过M单位时候后每个个体的能量,为了方便起见对1e9+7取模.
示例1
输入
1
5 1 3
1 1 1 1 1
输出
6 6 6 6 6
题解
矩阵快速幂。
观察给的公式和数据范围就可以知道可以用矩阵快速幂来搞，但是矩阵乘法复杂度为$O(n^3)$，又要乘上个$logM$，还有$200$组数据，复杂度炸了。
通过观察可以发现，这个矩阵是个循环矩阵，第二列和第一列是有关系的，也就是说只要计算第一列即可，因此矩阵乘法的复杂度降低到了$O(n^2)$。
总体复杂度是$O(T*n^2*logM)$。
#include <bits/stdc++.h>
using namespace std; const long long mod = 1e9 + 7;
const int maxn = 200 + 5;
int T;
int n, k;
long long M;
long long x[maxn];
long long ans[maxn]; struct Matrix {
int r, c;
long long a[maxn][maxn];
Matrix(int R, int C) {
r = R;
c = C;
for(int i = 0; i < r; i ++) {
for(int j = 0; j < c; j ++) {
a[i][j] = 0;
}
}
}
}; Matrix mul(const Matrix &a, const Matrix &b) {
Matrix res(0, 0);
res.r = a.r;
res.c = b.c;
memset(res.a, 0, sizeof res.a);
for(int i = 0; i < res.r; i ++) {
for(int j = 0; j < 1; j ++) {
for(int k = 0; k < a.c; k ++) {
long long sum = a.a[i][k] * b.a[k][j] % mod;
res.a[i][j] = (res.a[i][j] + sum) % mod;
}
}
}
for(int j = 1; j < res.c; j ++) {
for(int i = 1; i < res.r; i ++) {
res.a[i][j] = res.a[i - 1][j - 1];
}
res.a[0][j] = res.a[res.r - 1][j - 1];
}
return res;
} void init() {
Matrix A(n, n), B(n, n); for(int j = 0; j < n; j ++) {
for(int i = 0; i < n; i ++) {
if(i == j) continue;
int dis = min(abs(i - j), n - abs(i - j));
if(dis >= k) continue;
A.a[i][j] = k - dis;
}
} for(int i = 0; i < n; i ++) {
B.a[i][i] = 1;
} while(M) {
if(M & 1) B = mul(B, A);
M = M / 2;
A = mul(A, A);
}
/*
for(int j = 0; j < n; j ++) {
for(int i = 0; i < n; i ++) {
printf("%3lld ", B.a[i][j]);
}
printf("\n");
}
*/
for(int j = 0; j < n; j ++) {
for(int i = 0; i < n; i ++) {
long long sum = x[i] * B.a[i][j] % mod;
ans[j] = (ans[j] + sum) % mod;
}
}
} int main() {
scanf("%d", &T);
while(T --){
scanf("%d%lld%d", &n, &M, &k);
for(int i = 0; i < n; i ++) {
scanf("%lld", &x[i]);
ans[i] = 0;
}
init();
for(int i = 0; i < n; i ++) {
printf("%lld", ans[i]);
if(i < n - 1) printf(" ");
else printf("\n");
}
}
return 0;
}