循环矩阵+矩阵快速幂

题目链接：https://vjudge.net/problem/UVALive-3704

具体思路：用一维数组表示二维数组。

AC代码：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stdio.h>
#include<queue>
#include<stack>
using namespace std;
# define inf 0x3f3f3f3f
# define maxn 500+100
# define ll long long
ll n,m,d,k;
ll ans[maxn];
ll fir[maxn];
struct Matrix
{
ll a[maxn];
} t1,t2;
Matrix mul(Matrix w1, Matrix w2)
{
Matrix temp;
for(ll j=1; j<=n; j++)
{
temp.a[j]=0;
for(ll k=1; k<=n; k++)
{
temp.a[j]=(temp.a[j]+w1.a[k]*w2.a[(j-k+n)%n+1])%m;
}
}
return temp;
}
Matrix quickpow() // t1 - > n*n , t2 - > 1*n
{
Matrix tt=t2;
k--;
while(k)
{
if(k&1)
{
tt=mul(tt,t1);
}
t1=mul(t1,t1);
k=k>>1;
}
return tt;
}
int main()
{
while(~scanf("%lld%lld%lld%lld",&n,&m,&d,&k))
{
for(ll i=1; i<=n; i++)
{
scanf("%lld",&fir[i]);
}
for(ll i=1; i<=n; i++)
{
t1.a[i]=0;
}
for(ll i=1; i<=d+1; i++)
{
t1.a[i]=1;
}
for(ll i=1; i<=d; i++)
{
t1.a[n-i+1]=1;
}
t2=t1;
Matrix w=quickpow();
memset(ans,0,sizeof(ans));
for(ll i=1; i<=n; i++)
{
for(ll j=1; j<=n; j++)
{
ans[i]=(ans[i]+w.a[(i-j+n)%n+1]*fir[j])%m;
}
}
for(ll i=1; i<=n; i++)
{
printf("%lld",ans[i]);
if(i!=n)printf(" ");
}
printf("n");
}
return 0;
}

最后

以上就是超级手链为你收集整理的循环矩阵+矩阵快速幂的全部内容，希望文章能够帮你解决循环矩阵+矩阵快速幂所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。