题面
\(f_x=\begin{cases} 1&x\in\{1,2\}\\ f_{x-1}+f_{x-2}&x \geq 3\\ \end{cases}\)
求 \(1\times f_1+2\times f_2+3\times f_3+…+n\times f_n\) 。
解法
正常的Fibonacci 前 n 项和
-
\(loj\) 如果卡死了用这个： Fibonacci 前 n 项和
步入正题
再看这个发现就是变个形而已。
在已知 \(s_n=f_{n+2}-1\) 的前提下，可以极其简单的切了这道题。
原式
\(=s_n+s_n-s_{1}+s_n-s_{2}+…+s_n-s_{n-1}\)
\(=n\times s_n-\sum\limits_{i=1}^{n-1}s_i\)
\(=n\times s_n-\sum\limits_{i=3}^{n+1}f_{i}-1（∵ s_i=f_{i+2}-1）\)
\(=n\times s_n-(s_{n+1}-s_2-(n+1-3+1))\)
\(=n\times s_n-s_{n+1}+s_2+n-1\)
好的问题解决。
至于 \(s_n\) 的求法有很多种，用哪一种都可以，见上面的题解。
代码如下
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,P,ans[N][N],c[N][N],a[N][N],ans1,ans2;
void qpow(int b)
{
for(;b;b>>=1)
{
if(b&1)
{
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
(c[i][j]+=(ans[k][j]*a[i][k])%P)%P;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
ans[i][j]=c[i][j],c[i][j]=0;
}
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
(c[i][j]+=(a[i][k]*a[k][j])%P)%P;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
a[i][j]=c[i][j],c[i][j]=0;
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n),read(P);
a[1][1]=1;
a[2][1]=1;
a[1][2]=1;
a[2][2]=0;
for(int i=1;i<=2;i++)
ans[i][i]=1;
qpow(n+1);
ans1=(ans[2][1]+ans[2][2]-1)%P;
ans2=(ans[1][1]+ans[1][2]-1)%P;
cout<<((n*ans1)%P-ans2+2+n-1)%P;
}