[luogu_U15118]萨塔尼亚的期末考试

矩阵乘法

---

题面

$T$次询问，求出

$$\sum_{i=1}^n\frac{i}{\frac{n(n+1)}{2}}fib_i$$ （$fib$指斐波那契数列数列）

• $T\leq10^6,n\leq10^9$

解析

这$n$的范围显然要我们矩阵快速幂。
然而这式子需要转化：（别问我最后一步怎么证）

$$\sum_{i=1}^n\frac{2i}{n(n+1)}fib_i$$
$$\frac{2}{n(n+1)}\sum_{i=1}^nfib_i*i$$
$$\frac{2}{n(n+1)}(n*fib_{n+2}-fib_{n+3}+2)$$

用矩阵快速幂求个斐波那契数列都会吧。
复杂度$O(Tlogn)$。

然后花了n小时发现由于特判，我矩阵的表示在数列中位置的量被提前更新了
所以特判要写在最前面。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=998244353,N=2e6+100;
int n,las,ans[N],tar;
struct que{int n,id;bool operator < (const que &o) {return (n<o.n)||(n==o.n&&id<o.id);}}a[N];
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) 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[4][4];
  il Matrix(){memset(a,0,sizeof(a));}
  Matrix operator *(Matrix b)
  {
    Matrix c;
    fp(i,1,2)
      fp(j,1,2)
      fp(k,1,2)
      (c.a[i][j]+=1ll*a[i][k]*b.a[k][j]%mod)%=mod;
    return c;
  }
}S,T;
il int ksm(re int G,re int o)
{
  re int P=G;G=1;
  while(o)
    {
      if(o&1) G=1ll*G*P%mod;
      P=1ll*P*P%mod;
      o>>=1;
    }
  return G;
}
int main()
{
  S.a[1][1]=1;S.a[1][2]=1;
  re int q=gi();
  fp(i,1,q) a[i].n=gi(),a[i].id=i;
  sort(a+1,a+1+q);tar=2;
  fp(i,1,q)
    {
            n=a[i].n;
      if(n==1||n==2) {ans[a[i].id]=1;continue;}
            las=tar;tar=n+3;
      memset(T.a,0,sizeof(T.a));T.a[1][1]=T.a[1][2]=T.a[2][1]=1;
      re int k=tar-las;
      while(k)
    {
      if(k&1) S=S*T;
      T=T*T;
      k>>=1;
    }
            ans[a[i].id]=2*ksm(1ll*n*(n+1)%mod,mod-2)%mod*((1ll*n*S.a[1][2]%mod-S.a[1][1]+2+mod)%mod)%mod;
    }
  fp(i,1,q) printf("%d\n",ans[i]);
  return 0;
}