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

· · 题解

发现比赛的题解链接需要密码才能打开？

啊没办法看不了题解了怎么办。。。。自己写一篇好了qwq

就是这个题我们需要推一个式子：

\frac{\sum_{i=1}^n i\times F_i}{n\times(n-1)/2}

因为下面的分母很好求，所以。。。我们只需要知道怎么快速的求分子就行了。。。我们要降低复杂度qwq

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

证明：

\sum_{i=1}^n i\times F_i =n\times \sum_{i=1}^nF_i-(n-1)\times F_1-(n-2)\times F_2-...-1\times F_{n-1} =n\times \sum_{i=1}^nF_i-(\sum_{i=1}^{n-1}F_i+\sum_{i=1}^{n-2}F_i+...+\sum_{i=1}^2F_i+F_1) =n\times \sum_{i=1}^nF_i-(F_{n+1}-1+F_{n}-1+...+F_4-1+F_1) =n\times \sum_{i=1}^nF_i-(F_{n+1}+F_{n}+...+F_4+F_3+F_2+F_1-3-(n-2)) =n\times \sum_{i=1}^nF_i-F_{n+3}+1+n+1 =n\times F_{n+2}-F_{n+3}+2

这样一来就很简单了，因为数据很大，所以采用矩阵快速幂来加速斐波那契数列的运算，然后记得分子要求逆元qwq

下面贴上代码：（大家要注意及时取模啊，本蒻就是因为有一个取模忘写了结果炸成负数debug了好久来着。。。。）

#include<iostream>
#include<cstring>
#include<algorithm>
#define mod 998244353
using namespace std;
struct Node{long long t[3][3];};
Node res,poww;
long long ans[3],kkk[3];
int t;
long long mul(long long x,long long y)
{
    long long ans=1;
    while(y)
    {
        if(y&1) ans=x*ans%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
Node Mul(Node x,Node y)
{
    Node cur;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            cur.t[i][j]=0;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                cur.t[i][j]=(cur.t[i][j]+(x.t[i][k]*y.t[k][j])%mod)%mod;
    return cur;
}
void solve()
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            ans[i]=(ans[i]+(kkk[j]*(res.t[i][j])%mod)%mod)%mod;
}
int main()
{

    scanf("%d",&t);
    for(int c=1;c<=t;c++)
    {
        long long n;
        memset(ans,0,sizeof(ans));
        memset(kkk,0,sizeof(kkk));
        for(int i=0;i<=2;i++)
            for(int j=0;j<=2;j++)
                poww.t[i][j]=0,res.t[i][j]=0;
        kkk[1]=kkk[2]=1;//[1]=a_n+3,[2]=a_n+2 
        res.t[1][1]=res.t[2][2]=1;//单位矩阵 
        poww.t[1][1]=poww.t[1][2]=poww.t[2][1]=1;//快速幂矩阵 
        scanf("%lld",&n);
        long long he=(n*(n+1)/2)%mod;
        long long k=mul(he,mod-2);//求逆元 
        long long cnt=n+1;
        while(cnt)
        {
            if(cnt&1) res=Mul(res,poww);
            poww=Mul(poww,poww);
            cnt>>=1;
        }
        solve();
        k=k*((n*ans[2]%mod+mod-(ans[1]%mod)+2)%mod);
        printf("%lld\n",k%mod);
    }
    return 0;
}