题解 P4834 【萨塔尼亚的期末考试】

BotDand

$\text{Problems}$

给出 $n$ ，求 $\frac{\sum_ {i=1}^ {n} i \times F_ {i}}{n\times(n+1)/2}$ 。

$\text{Answer}$

$\sum_ {i=1}^{n} i \times F_ {i}=n \times F_ {n+2}-F_ {n+3}+2$

证明：

当 $n=1$ 时，原命题显然成立。

设 $n=k$ 时原命题成立

令 $f_ {n}=\sum_ {i=1}^{n} i \times F_ {i}$

则

$$
f_ {k+1}=f_ {k}+F_ {k+1} \times (k+1)\
=k \times F_ {k+2}-F_ {k+3}+2+F_ {k+1} \times (k+1)\
=k \times F_ {k+3}-F_ {k+3}+2+F_ {k+1}\
=k \times F_ {k+3}-F_ {k+2}+2
$$

所以原命题成立。

这玩意用矩阵乘法算一下即可。

然后 $n\times(n+1)/2$ 求一下逆元即可。

注意取模。

开了 O2 居然跑了最优解/yun

$\text{Code}$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mo=998244353;
int t,n;
int A,B;
int m;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void print(int x)
{
    write(x);
    putchar('\n');
}
int ksm(int a,int b,int mo)
{
    int ans=1,x=a;
    while(b)
    {
        if(b&1) ans=ans%mo*x%mo;
        x=x%mo*x%mo;b>>=1;
    }
    return ans;
}
struct arr
{
    int a[3][3];
    arr() {memset(a,0,sizeof(a));}
    arr operator *(const arr &b) const
    {
        arr c;
        for(int i=1;i<=2;++i)
            for(int j=1;j<=2;++j)
                for(int k=1;k<=2;++k)
                    c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mo)%mo;
        return c;
    }
}a,ans;
inline void work()
{
    n=read();
    B=ksm((((n+1)*n/2)%mo),mo-2,mo);
    a.a[1][1]=1;a.a[1][2]=1;
    a.a[2][1]=1;a.a[2][2]=0;
    ans.a[1][1]=1;ans.a[1][2]=0;
    ans.a[2][1]=0;ans.a[2][2]=1;
    m=n+1;
    while(m)
    {
        if(m&1) ans=ans*a;
        a=a*a;m>>=1;
    }
    A=(n*ans.a[1][1]%mo+mo-(ans.a[1][1]+ans.a[1][2])%mo+2+mo)%mo;
    print(A*B%mo);
}
signed main()
{
    t=read();
    while(t--) work();
}