题解 P2461 【[SDOI2008]递归数列】

ysner · 2017-08-01 07:22:17 · 题解

看到楼下的题解没画出矩阵图，而矩阵是矩阵快速幂最重要的一环，我就来补一发吧。

本题主要是构造矩阵，我们只需要把那一段式子看成两个前缀和相减， 然后就直接矩阵连乘。

直接对那个k+1阶矩阵快速幂即可，注意初始化矩阵为单位矩阵，即主对角线（左上到右下）都为1其他都为0。

另外，很多量要开long long。

当然，为了卡时间，我inline、register、读入优化齐用，卡到了63ms。。。膜拜12ms的rank 1。。。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
using namespace std;
int b[15]={},c[15]={},sum[15]={},K,p,ansn,ansm;
ll n,m;
il ll gi()//读入优化开long long，否则只有20分
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
struct matrix//矩阵乘法标准模板
{
     int a[16][16];
    matrix ()
    {
        memset(a,0,sizeof(a));
    }
    int *operator [](int x)
    {
        return a[x];
    }
    matrix operator *(matrix &b)
    {
        matrix c;
        for (re int i=0;i<=K;i++)
          for (re int j=0;j<=K;j++)
            for (re int k=0;k<=K;k++)
              c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%p;
        return c;
    }
}S,T;
il void init()
{
    for (re int i=0;i<K;i++)
      S[0][i]=b[i];
    S[0][K]=sum[K-1];
    for (re int i=1;i<=K;i++)
      for (re int j=0;j<=K;j++)
        S[i][j]=0;
    for (re int i=0;i<=K;i++)
      for (re int j=0;j<=K;j++)
        if (i==j+1) T[i][j]=1;
        else T[i][j]=0;
    for (re int i=0;i<K;i++)
      T[i][K-1]=T[i][K]=c[K-i-1];
    T[K][K-1]=0;T[K][K]=1;
}
int main()
{
    K=gi();
    for (re int i=0;i<K;i++)
      b[i]=gi(),sum[i]=b[i]+sum[i-1];
    for (re int i=0;i<K;i++)
      c[i]=gi();
    m=gi();n=gi();p=gi();
    m-=K+1;n-=K;
    if (m<=0) ansm=sum[m+K-1];
    else 
    {
        init();
        while (m)
        {
            if (m&1) S=S*T;
            T=T*T;
            m>>=1;
        }
        ansm=S[0][K];
    }
    if (n<=0) ansn=sum[n+K-1];
    else 
    { 
        init();
        while (n)//快速幂
        {
            if (n&1) S=S*T;
            T=T*T;
            n>>=1;
        }
        ansn=S[0][K];
    }
    printf("%d",(ansn-ansm+p)%p);
    return 0;
}