自动搬运

查看原文

来自洛谷，原作者为

	ZqlwMatt **

搬运于2025-08-24 21:53:37，当前版本为作者最后更新于2018-03-12 20:40:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：给定常数$a_{i}$，$w_{i}$ $(i=1$~$n)$，及递推式：$w_{k}=\sum_{i=1}^{n} a_{i}×w_{k-i}$ 给出一个$m$求$a_{m}$。

说句废话：然而前3个过这道题的都是同机房的（#逃。

解法一：

构造矩阵+矩阵快速幂

• 矩阵构造如下：（我们可以将递推式转换一下......

$\begin{pmatrix}w_{n} & w_{n-1} & ... & ... & w_{i+1} & w_{i}\end{pmatrix}×\begin{pmatrix}a_{1} & 1 & 0 & 0 & 0 & 0\\ a_{2} & 0 & 1 & 0 & 0 & 0\\ ... & 0 & 0 & ... & 0 & 0\\ ... & 0 & 0 & 0 & ... & 0\\a_{n-1} & 0 & 0 & 0 & 0 &1\\ a_{n} & 0 & 0 & 0 & 0 & 0\end{pmatrix}=\begin{pmatrix}w_{n+1} & w_{n} & ... & ... & w_{i+2} & w_{i+1}\end{pmatrix}$

将递推式转换成矩阵，然后利用快速幂可以大大优化递推效率。。。

时间复杂度：Θ$(n^{3}×log$ $m)$

评测详情:R6166875

Time: 340ms / Memory: 2089KB

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
const int N=101,p=4147;
int n,m,w[N],x;
struct Matrix{
    int k[N][N];
    Matrix(){
        memset(k,0,sizeof(k));
    }
    inline void Memset(){rep(i,1,n)k[i][i]=1;}
}res;
Matrix operator *(Matrix a,Matrix b){
    Matrix rhy;
    rep(i,1,n)
        rep(j,1,n){
            rep(z,1,n)
      			rhy.k[i][j]+=a.k[i][z]*b.k[z][j];
      		rhy.k[i][j]%=p;
      	}
    return rhy;
}
Matrix qmod(Matrix a,int k){
    Matrix tmp;
    tmp.Memset();
    while(k){
        if(k&1)	tmp=tmp*a;
        a=a*a;
        k>>=1;
    }
    return tmp;
}

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n)	scanf("%d",w+i);
    rep(i,1,n-1)	res.k[i][i+1]=1;
    rep(i,1,n){
        scanf("%d",&x);
        res.k[i][1]=x;
    }
    res=qmod(res,m-n);
    int ans=0;
    rep(i,1,n)
        ans=(ans+res.k[i][1]*w[i])%p;
    printf("%d\n",ans);
}

解法二：

暴力递推+吸氧优化（#一本正经

时间复杂度：Θ$(n×m)$

评测详情:R6158787

Time: 10968ms / Memory: 39878KB

// luogu-judger-enable-o2
#include<cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
int n,m,a[102],w[10000002];
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n)	scanf("%d",w+n+1-i);
    rep(i,1,n)	scanf("%d",a+i);
    rep(i,n+1,m){
        rep(z,1,n)
            w[i]+=a[z]*w[i-z];
        w[i]%=4147; 
    }
    printf("%d",w[m]);
}