Description

Analysis

10分：暴力+把m和n输反，你将获得10分的好成绩(Just like me.)

70分：暴力+把m和n输对，你将获得70分的好成绩

100分：矩阵加速

设

$ T(n)=1F_1+2F_2+3F_3+......+nF_n $

$S(n)=F_1+F_2+F_3+......+F_n$

则有：

$n*S(n)-T(n)=(n-1)*F_1+(n-2)*F_2+(n-3)*F_3+......+1*F_{n-1}$

移项可得

$T(n)=n*S(n)-(n-1)*F_1+(n-2)*F_2+(n-3)*F_3+......+1*F_{n-1}$

客官且慢，观察可以发现

$(n-1)*F_1+(n-2)*F_2+(n-3)*F_3+......+1*F_{n-1}$

不就是S(1)~S(n-1)的前缀和么

所以再设

$G(n)=G(n-1)+S(n)$

但一项一项来太慢了

用矩阵加速吧

于是设矩阵

$[F(n-1),F(n),S(n),G(n)]$

转移矩阵自然出来了

$[0,1,1,1]$

$[1,1,1,1]$

$[0,0,1,1]$

$[0,0,0,1]$

差一点就成阶梯矩阵了呢

So：

70：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll n,mod,now,ans=3,a=1,b=1;

int main(){

	cin>>n>>mod;

	if(n==1){cout<<1%mod;return 0;}

	if(n==2){cout<<3%mod;return 0;}

	for(register int i=3;i<=n;++i){

		now=(a+b)%mod;

		a=b,b=now,ans=(ans+i%mod*now%mod)%mod;

	}

	cout<<ans;

	return 0;

}

100：

#include<cstdio>

#include<cstring>

#define re register

#define in inline

#define int long long

in int read()

{

	int s(0),b(0);char ch;

	do{ch=getchar();if(ch=='-')b=-1;}while(ch<'0'||ch>'9');

	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

	return b?-s:s;

}

int n,m;

struct mat{

	int v[5][5];

	mat operator*(const mat &t)const

		{

			mat c;

			memset(c.v,0,sizeof(c.v));

			for(re int i=1;i<=4;++i)

				for(re int j=1;j<=4;++j)

					for(re int k=1;k<=4;++k)

						c.v[i][j]=(c.v[i][j]+v[i][k]*t.v[k][j]%m)%m;

			return c;

		}

}I,S,T;

in mat ksm(mat ba,int k)

{

	mat ans=I;

	while(k)

	{

		if(k&1) ans=ans*ba;

		k>>=1;

		ba=ba*ba;

	}

	return ans;

}

signed main()

{

	n=read(),m=read();

	I.v[1][1]=I.v[2][2]=I.v[3][3]=I.v[4][4]=1;

	S.v[1][1]=S.v[1][2]=S.v[1][3]=S.v[1][4]=1;

	T.v[1][1]=T.v[2][1]=T.v[2][2]=T.v[3][1]=T.v[3][2]=T.v[3][3]=T.v[3][4]=T.v[4][3]=1;

	if(n==1){

		printf("%lld\n",1ll%m);

		return 0;

	}

	S=S*ksm(T,n-2);

	int pn1=S.v[1][1];

	S=S*T;

	printf("%lld\n",(n%m*S.v[1][2]%m-pn1+m)%m);

	return 0;

}

巴特西

Loj10222佳佳的 Fibonacci

Description

Analysis

70：

100：

最新文章

热门文章