题解 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; } ```