哈尔滨理工大学第七届程序设计竞赛决赛(网络赛-高年级组)I - 没有名字

题目描述

tabris实在是太菜了,没打败恶龙,在绿岛也只捡到一块生铁回去了,为了不在继续拉低acimo星球的平均水平逃离地球,来到了Sabi星球.

在这里tabris发现了一种神奇的生物,这种生物不需要与外界交流,种群间不同个体能互相维持生命存在及提供生长所需的能量.

每个种群有N个不同个体,围成一个圈,每隔一个单位时间都会生长.

在一个单位时间里,每个个体会向两边辐射能量,辐射范围与强度均为K,随着距离的增加辐射强度会减小,距离每增加1辐射强度减小1 ,在这单位时间通过辐射接受的能量会保留,最开始的能量会消耗掉。

对于两个个体a、b,其中a对b的辐射会使b增加【辐射强度×a最开始的能量值】.

总体的改变可以表示成
 
哈尔滨理工大学第七届程序设计竞赛决赛(网络赛-高年级组)I - 没有名字
 

注:[∗] * 为真时为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;
}

  

上一篇:Hadoop学习(5)-- Hadoop2


下一篇:哈尔滨理工大学第七届程序设计竞赛(G.Great Atm)