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

· · 题解

link

Description

简化题意：

求 \dfrac{\sum\limits_{i=1}^{n} (i \times F_i)}{\frac{n \times (n+1)}{2}} 对 998244353 取模的值，其中 F_i 是斐波那契数列的第 i 项。

Solution

先推式子：

对于斐波那契，有 S_n = \sum\limits_{i=1}^{n} F_i = F_{n+2} - 1。

:::info[prof.]

\begin{aligned} S_n &= \sum\limits_{i=1}^{n} F_i\\ &= \sum\limits_{i=1}^{n} (F_{i+2}-F_{i+1})\\ &= F_{n+2} - F_2\\ &= F_{n+2} - 1 \end{aligned}

证毕。 :::

把前缀和代到 \sum\limits_{i=1}^{n} (i \times F_i) 里推：

\begin{aligned} \sum\limits_{i=1}^{n} (i \times F_i) &= \sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n} F_i\\ &= \sum\limits_{i=1}^{n} (S_n-S_{i-1})\\ &= \sum\limits_{i=1}^{n} (F_{n+2} - 1 - F_{i+1} + 1)\\ &= \sum\limits_{i=1}^{n} (F_{n+2} - F_{i+1})\\ &= n \times F_{n+2} - \sum\limits_{i=1}^{n} F_{i+1}\\ &= n \times F_{n+2} - (S_{n+1} - 1)\\ &= n \times F_{n+2} - (F_{n+3} - 2)\\ &= n \times F_{n+2} - F_{n+3} + 2 \end{aligned}

所以只需要求 F_{n+2},F_{n+3}，矩阵快速幂求。

注意到：

\begin{bmatrix} F_2\\F_1 \end{bmatrix} \times \begin{bmatrix} 1 \ 1\\1 \ 0 \end{bmatrix}^{n+1}=\begin{bmatrix} F_{n+3}\\F_{n+2} \end{bmatrix}

所以只需要一次快速幂就可以了。

Code

:::success[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef double db;
typedef __int128 i128;
const ll inf=9e18,mod=998244353;
const i128 Inf=1e35;
struct matrix
{
    ll a[2][2];
    void init()
    {
        memset(a,0,sizeof(a));
    }
    void unit()
    {
        init();
        a[0][0]=a[1][1]=1;
    }
    matrix operator*(matrix other) const
    {
        matrix ans;
        ans.init();
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++) ans.a[i][j]=(ans.a[i][j]+a[i][k]*other.a[k][j]%mod)%mod;
            }
        }
        return ans;
    }
};
matrix qpow(matrix a,ll b)
{
    matrix ans;
    ans.unit();
    while(b)
    {
        if(b%2) ans=ans*a;
        a=a*a;
        b/=2;
    }
    return ans;
}
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b%2) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
ll inv(ll a)
{
    return qpow(a,mod-2);
}
ll t,n;
void solve()
{
    cin>>n;
    matrix base,fib;
    base.init(),fib.init();
    base.a[0][0]=base.a[0][1]=base.a[1][0]=fib.a[0][0]=fib.a[0][1]=1;
    base=qpow(base,n+1),fib=fib*base;
    ll fib1=fib.a[0][0],fib2=fib.a[0][1],tot=inv((n*(n+1)/2)%mod);
    cout<<((n*fib2-fib1+2+mod)%mod*tot)%mod<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--) solve();
}

:::