题解 P3873 【[TJOI2010]天气预报】

· · 题解

题意：给定常数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]);
}