考虑一个简单的整数问题2中的思路:
令 $T(n) = 1f_1 + 2f_2 + … +nf_n, S(n) = f_1 + f_2 + … + f_n$
将S求和可得:
$S(1)+S(2)+…+S(n)=nf_1 + (n-1)f2 + … +1f_n$
观察到:
$ (n+1)*S_n - T(n)=nf_1+(n-1)f_2+…+f_1=S_1+S_2+…+S_n $
$T(n)=(n+1)S_n-(S1+S2+…+Sn)$
不难得到: $S_n=f_{n+2}-1 $
$\rightarrow (S_1+S_2+…S_n)=(f_3-1+f_4-1+…+f_{n+2}-1)$
$=(f_1+f_2+…+f_{n+2}-(n+2))=S_{n+2}-(n+2)=f_{n+4}-(n+3)$
$T(n)=(n+1)(f_{n+2}-1)-(f_{n+4}-(n+3))=(n+1)f_{n+2}-f_{n+4}+2=nf_{n+2}-f_{n+3}+2$
因此只需要求出$f_{n+2},f_{n+3}$的值即可
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll res[2][2] = {1,0,0,1};
ll a[2][2] = {0,1,1,1}, tmp[2][2];
int n,m;
void mul(ll a[][2], ll b[][2])
{
memset(tmp,0,sizeof tmp);
for(int i = 0 ; i < 2 ; i ++)
{
for(int j = 0 ; j < 2 ; j ++)
{
for(int k = 0 ; k < 2 ; k ++)
tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j] % m) % m;
}
}
memcpy(b,tmp,32);
}
int main()
{
cin >> n >> m;
int t = n+2;
while(t)
{
if(t&1) mul(a,res);
mul(a,a);
t >>= 1;
}
ll ans = ((n*res[0][1]-res[1][1]+2)%m+m)%m;
cout << ans;
}