自动搬运

查看原文

来自洛谷，原作者为

	风浔凌 **

搬运于2025-08-24 22:04:26，当前版本为作者最后更新于2018-09-27 19:38:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

因为下面的分母很好求，所以。。。我们只需要知道怎么快速的求分子就行了。。。我们要降低复杂度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;
}