bzoj 4161 Shlw loves matrixI——常系数线性齐次递推

时间：2022-07-31 18:16:20

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4161

还是不能理解矩阵……

关于不用矩阵理解的方法：https://blog.csdn.net/joker_69/article/details/80869814

关于这道题：https://blog.csdn.net/sdfzyhx/article/details/63697273

现在只会 O(k2logn) 的做法。

很多题解的写法是快速幂到多项式的 n-(k-1) 次，用递推式暴力把给出的 \(h_0,...,h_{k-1}\) 扩展到 \( h_0,...,h_{2*(k-1)} \) ，然后用 \( h_{k-1},...,h_{2*(k-1)} \) 乘上刚才做出的多项式得到答案。关于这个的理解：

　　现在的多项式可以看作是转移矩阵 M 的 n-(k-1) 次幂的第一列。考虑到原来的值向量对应位乘上该多项式就是第 n-(k-1) 次项的答案，所以大概可以这样考虑？

　　所以这个多项式可以在 \( h_i,...,h_{i+k-1} \) 乘上它的情况下得到 \( h_{i+n-(k-1)} \) 的答案。

但直接把多项式乘到 n 次，然后用初始的 \( h_0,...,h_{k-1} \) 来乘，在 bzoj 上似乎比上述方法稍微快一点。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=,mod=1e9+;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int n,k,a[N],h[N],b[N],c[N],ans[N];

void Mul(int *u,int *v)

{

  memset(c,,sizeof c);

  for(int i=;i<k;i++)

    for(int j=;j<k;j++)

      c[i+j]=(c[i+j]+(ll)u[i]*v[j])%mod;

  for(int i=*(k-);i>=k;i--)

    if(c[i])

      for(int j=;j<=k;j++)

    c[i-j]=(c[i-j]+(ll)c[i]*a[j])%mod;

  memcpy(u,c,sizeof (int)*k);

}

int main()

{

  n=rdn();k=rdn();

  for(int i=;i<=k;i++)a[i]=upt(rdn());//upt!!!

  for(int i=;i<k;i++)h[i]=upt(rdn());

  if(n<k){printf("%d\n",h[n]);return ;}

  /*for(int i=k,lm=2*(k-1);i<=lm;i++)

    for(int j=1;j<=k;j++)

      h[i]=(h[i]+(ll)a[j]*h[i-j])%mod;

      if(n<=2*(k-1)){printf("%d\n",h[n]);return 0;}*/

  b[]=; ans[]=;

  /*n-=k-1;*/

  while(n){ if(n&)Mul(ans,b); Mul(b,b); n>>=;}

  int prn=;

  /*for(int i=0;i<k;i++)

    prn=(prn+(ll)h[k-1+i]*ans[i])%mod;*/

  for(int i=;i<k;i++)

    prn=(prn+(ll)h[i]*ans[i])%mod;

  printf("%d\n",prn);

  return ;

}

相关文章