时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
tabris实在是太菜了,没打败恶龙,在绿岛也只捡到一块生铁回去了,为了不在继续拉低acimo星球的平均水平逃离地球,来到了Sabi星球.
在这里tabris发现了一种神奇的生物,这种生物不需要与外界交流,种群间不同个体能互相维持生命存在及提供生长所需的能量.
每个种群有N个不同个体,围成一个圈,每隔一个单位时间都会生长.
在一个单位时间里,每个个体会向两边辐射能量,辐射范围与强度均为K,随着距离的增加辐射强度会减小,距离每增加1辐射强度减小1 ,在这单位时间通过辐射接受的能量会保留,最开始的能量会消耗掉。
对于两个个体a、b,其中a对b的辐射会使b增加【辐射强度×a最开始的能量值】.
总体的改变可以表示成
a
[
i
]
′
=
∑
j
=
1
N
a
[
j
]
×
(
K
?
d
i
s
(
i
,
j
)
)
×
[
i
!
=
j
]
×
[
K
?
d
i
s
(
i
,
j
)
>
0
]
a[i]^{'}=\sum_{j=1}^{N}a[j]\times (K-dis(i,j))\times [i!=j]\times [K-dis(i,j)>0]
a[i]′=j=1∑N?a[j]×(K?dis(i,j))×[i!=j]×[K?dis(i,j)>0]
注：[?] * 为真时为1 *为假时为0
现在tabris想知道经过M单位时间后,每个个体的能量值是多少.
输入描述:
输入一个T,表示测试数据的组数
每个测试数据第一行包含三个正整数
N
,
M
,
K
.
N,M,K.
N,M,K.
接下来一行包含N个正整数a[i];
T
∈
[
1
,
200
]
T\in[1,200]
T∈[1,200]
N
∈
[
1
,
200
]
N\in[1,200]
N∈[1,200]
K
∈
[
1
,
?
n
2
?
]
K∈[1,?\frac n2?]
K∈[1,?2n??]
M
∈
[
1
,
1
0
18
]
M∈[1,10^{18}]
M∈[1,1018]
a
[
i
]
∈
[
1
,
1
0
6
]
a[i]∈[1,10^6]
a[i]∈[1,106]
输出描述:
对每组测试样例输出经过M单位时候后每个个体的能量,为了方便起见对
1
e
9
+
7
1e9+7
1e9+7取模.
示例1
输入
1
5 1 3
1 1 1 1 1
输出
6 6 6 6 6
思路：第一想法是构造出转移矩阵，然后利用快速幂求解，但复杂度达到
O
(
T
?
N
3
?
l
o
g
2
(
m
)
)
O(T*N^3*log_2(m))
O(T?N3?log2?(m))，会TLE。
考虑到题目中
N
N
N个数构成了一个环，所以转移矩阵其实也是由矩阵中第一列的值循环
N
N
N次构成的，所以我们只需要求出
M
M
M时间后第一列的值，其它列的值都可以由第一列循环得到，复杂度
O
(
T
?
N
2
?
l
o
g
2
(
m
)
)
O(T*N^2*log_2(m))
O(T?N2?log2?(m))。
#include<bits/stdc++.h>
#define lson (k<<1)
#define rson (k<<1)+1
#define sz(x) int(x.size())
#define pii pair<ll,ll>
using namespace std;
const int MAX=1e5+10;
const int MOD=1e9+7;
const double PI=acos(-1.0);
typedef long long ll;
struct lenka
{
int n,a[200][200];
lenka(int _){
n=_;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)a[i][j]=0;
}
};
lenka operator*(const lenka&a,const lenka&b)
{
lenka c(a.n);
for(int k=0;k<c.n;k++)
for(int i=0;i<c.n;i++)
{
c.a[i][0]+=1ll*a.a[i][k]*b.a[k][0]%MOD;
c.a[i][0]%=MOD;
}
for(int j=1;j<c.n;j++)
for(int i=0;i<c.n;i++)c.a[i][j]=c.a[(i-1+c.n)%c.n][j-1];
return c;
}
lenka POW(ll n,lenka x)
{
lenka r(x.n);
for(int i=0;i<x.n;i++)r.a[i][i]=1;
while(n)
{
if(n&1)r=r*x;
x=x*x;
n>>=1;
}
return r;
}
int main()
{
int T;
cin>>T;
while(T--)
{
ll n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
lenka a(n);
for(int i=0;i<n;i++)scanf("%d",&a.a[0][i]);
lenka r(n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
int dis=min(1ll*abs(i-j),n-abs(i-j));
r.a[j][i]=(k-dis)*(i!=j)*(k>dis);
}
r=POW(m,r);
lenka c(n);
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
c.a[i][j]+=1ll*a.a[i][k]*r.a[k][j]%MOD;
if(c.a[i][j]>=MOD)c.a[i][j]-=MOD;
}
for(int i=0;i<n;i++)printf("%d%c",c.a[0][i]," \n"[i+1==n]);
}
return 0;
}
