P2461 [SDOI2008]递归数列 矩阵乘法+构造

还好$QwQ$

---

思路：矩阵快速幂

提交：1次

题解：

如图：

注意$n,m$如果小于$k$就不要快速幂了，直接算就行、。。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ull unsigned long long

#define ll long long

#define R register ll

using namespace std;

#define pause (for(R i=1;i<=10000000000;++i))

#define In freopen("NOIPAK++.in","r",stdin)

#define Out freopen("out.out","w",stdout)

namespace Fread {

static char B[<<],*S=B,*D=B;

#ifndef JACK

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

#endif

inline ll g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    if(ch==EOF) return EOF; do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

} inline bool isempty(const char& ch) {return (ch<=||ch>=);}

inline void gs(char* s) {

    register char ch; while(isempty(ch=getchar()));

    do *s++=ch; while(!isempty(ch=getchar()));

}

} using Fread::g; using Fread::gs;

namespace Luitaryi {

const int N=;

int k,mod,b[N],c[N];

ll n,m,sumn,summ,sum[N];

ll ans[N],s[N],a[N][N],mem[N][N];

inline void mul(ll a[][N],ll b[][N]) {

    R tmp[N][N]; memset(tmp,,sizeof(tmp));

    for(R i=;i<=k+;++i) for(R l=;l<=k+;++l) for(R j=;j<=k+;++j)

        tmp[i][j]=(tmp[i][j]+a[i][l]*b[l][j])%mod;

    memcpy(a,tmp,sizeof(tmp));

}

inline void qpow(ll p) {

    R ret[N][N]; memset(ret,,sizeof(ret));

    for(R i=;i<=k+;++i) ret[i][i]=;

    for(;p;p>>=,mul(a,a)) if(p&) mul(ret,a);

    memcpy(a,ret,sizeof(a));

}

inline void main() {

    k=g(); for(R i=;i<=k;i++) b[i]=g();

    for(R i=;i<=k;++i) c[i]=g();

    m=g()-k-,n=g()-k,mod=g();

    const int M=mod;

    for(R i=;i<=k;++i) sum[i]=(b[i]+sum[i-])%M;

    for(R i=;i<=k;++i) s[i]=b[i]%M; s[k+]=sum[k]%M;

    for(R i=;i<k;++i) a[i+][i]=;

    for(R i=;i<=k;++i) a[i][k]=a[i][k+]=c[k-i+]%M; a[k+][k+]=;

    if(n<=) return (void)printf("%lld\n",((sum[k+n-]-sum[k+m-])%M+M)%M);

    memcpy(mem,a,sizeof(a));

    qpow(n); for(R i=;i<=k+;++i) for(R j=;j<=k+;++j) ans[j]=(ans[j]+s[i]*a[i][j])%M; sumn=ans[k+];

    if(m<=) return (void)printf("%lld\n",((sumn-sum[k+m])%M+M)%M);

    memset(ans,,sizeof(ans)); memcpy(a,mem,sizeof(a));

    qpow(m); for(R i=;i<=k+;++i) for(R j=;j<=k+;++j) ans[j]=(ans[j]+s[i]*a[i][j])%M; summ=ans[k+];

    printf("%lld\n",((sumn-summ)%M+M)%M);

}

}

signed main() {

    Luitaryi::main();

    return ;

}

---

2019.07.21