题解 P5678 【[GZOI2017]河神】

· · 题解

这道题其实就是单纯考察的对矩阵的理解

在广义的矩阵运算中只要使其满足结合律就能像普通的矩阵运算一样操作

（实际上不难发现，这东西很想NOIonline的某道题的矩阵的乘法和加法的定义一样

我们考虑转移矩阵咋构建

实际上我们要使得在转移矩阵中的前 k-1 个 满足A_n-1 \to A_n，最后一个满足我们的递推关系（其实就和一般的一样

在这里我们只考虑一个东西，就是说找到加法和乘法的单位元

实际上这里的加法的单位元就是 -1 ,乘法的就是 0

那么我们就是将

A= \left\{ \begin{matrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ a_{1} & a_{2} & a_{3} & \cdots & a_{n} \end{matrix} \right\}

变为

A= \left\{ \begin{matrix} 0 & -1 & 0 & \cdots & 0 \\ 0 & 0 & -1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -1 \\ a_{1} & a_{2} & a_{3} & \cdots & a_{n} \end{matrix} \right\}

复杂度就是O(k^3logn)

code:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,k;

struct M
{
  long long s[110][110],r,c;
  void clear()
  {
    for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) s[i][j]=0;
  }
}ans,Ye;

M operator * (const M &x,const M &y)
{
  M now;
  now.clear();
  now.r=x.r;
  now.c=y.c;
  for(int k=1;k<=x.c;k++)
  {
    for(int i=1;i<=x.r;i++)
    {
      for(int j=1;j<=y.c;j++)
      {
        now.s[i][j]|=x.s[i][k]&y.s[k][j];
      }
    }
  }
  return now;
}

M ksm(M a,int b)
{
  M ans=a;
  b--;
  while(b)
  {
    if(b&1) ans=ans*a;
    a=a*a;
    b>>=1;
  }
  return ans;
}

int main()
{
  scanf("%d%d",&n,&k);
  ans.clear();
  ans.r=1;
  ans.c=k;
  for(int i=1;i<=k;i++) scanf("%lld",&ans.s[1][i]);
  Ye.clear();
  Ye.r=k;
  Ye.c=k;
  for(int i=1;i<=k;i++)
  {
    long long now;
    scanf("%lld",&now);
    Ye.s[i][k]=now;
  }
  for(int i=1;i<=k;i++)
  {
    for(int j=1;j<=k;j++)
    {
      if(i==j+1) Ye.s[i][j]=-1;
    }
  }
  if(n<=k)
  {
    printf("%lld",ans.s[1][n]);
  }
  else
  {
    M now=ans*ksm(Ye,n-k+1);
    printf("%lld",now.s[1][k]);
  }
}