$\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();
}