結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー takayuta1999takayuta1999
提出日時 2015-04-26 23:22:18
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 39 ms / 5,000 ms
コード長 2,846 bytes
コンパイル時間 340 ms
コンパイル使用メモリ 43,064 KB
実行使用メモリ 7,856 KB
最終ジャッジ日時 2024-07-05 01:39:15
合計ジャッジ時間 1,975 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:111:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  111 |         scanf("%d %lld",&n,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:112:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  112 |         for(int i=0;i<n;i++) scanf("%d",&A[i]);
      |                              ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 70
#define MOD 1000000007
#define MX 1000005

using namespace std;
typedef long long int ll;

struct Matrix
{
	int n;
	ll A[SIZE][SIZE];
	
	ll mpow(ll x,ll t)
	{
		if(t==0) return 1;
		ll ret=mpow(x,t/2);
		ret=ret*ret%MOD;
		if(t%2==1) ret=ret*x%MOD;
		return ret;
	}
	ll inv(ll x)
	{
		return mpow(x,MOD-2);//if MOD is a prime number
	}
	void init(int m)
	{
		n=m;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				A[i][j]=0;
			}
		}
	}
	void add(int a,int b,ll x)
	{
		A[a][b]+=x;
		if(A[a][b]>=MOD) A[a][b]-=MOD;
	}
};
Matrix SUM_mat,PR_mat;
void product(Matrix&A,Matrix&B)
{
	int n=A.n;
	PR_mat.init(n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			PR_mat.A[i][j]=0;
			for(int k=0;k<n;k++)
			{
				PR_mat.A[i][j]+=A.A[i][k]*B.A[k][j]%MOD;
				if(PR_mat.A[i][j]>=MOD) PR_mat.A[i][j]-=MOD;
			}
		}
	}
}
void sumsum(Matrix&A,Matrix&B)
{
	int n=A.n;
	SUM_mat.init(n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			SUM_mat.A[i][j]=0;
			for(int k=0;k<n;k++)
			{
				SUM_mat.A[i][j]+=(A.A[i][k]+B.A[k][j])%MOD;
				if(SUM_mat.A[i][j]>=MOD) SUM_mat.A[i][j]-=MOD;
			}
		}
	}
}
Matrix mt[SIZE];
void mpow(Matrix&M,ll t,int dep)
{
	if(t==1)
	{
		mt[dep]=M;
		return;
	}
	mpow(M,t/2,dep+1);
	product(mt[dep+1],mt[dep+1]);
	mt[dep]=PR_mat;
	if(t%2==1)
	{
		product(mt[dep],M);
		mt[dep]=PR_mat;
	}
}
Matrix mat;
int A[MX],F[MX];
int n;
ll k;

int get(int i,int j)
{
	if(i==n-1) return 1;
	return i+1==j?1:0;
}
int main()
{
	scanf("%d %lld",&n,&k);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	if(k<MX)
	{
		int now=0,sum=0;
		for(int i=0;i<n;i++)
		{
			now+=A[i];
			sum+=A[i];
			sum%=MOD;
			now%=MOD;
			F[i]=A[i];
		}
		for(int i=n;i<k;i++)
		{
			F[i]=now;
			sum+=F[i];
			sum%=MOD;
			if(i+1==k) break;
			now+=MOD-F[i-n];
			now%=MOD;
			now+=F[i];
			now%=MOD;
		}
		printf("%d %d\n",now,sum);
	}
	else
	{
		mat.init(n*2);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				mat.add(i,j,get(i,j));
			}
		}
		for(int i=n;i<n*2;i++)
		{
			for(int j=0;j<n*2;j++)
			{
				mat.add(i,j,i%n==j%n?1:0);
			}
		}
		mpow(mat,k-1,0);
		Matrix am,sm;
		am.init(n);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				ll vl=0;
				for(int k=0;k<2*n;k++)
				{
					vl+=mt[0].A[i][k]*(k%n==j?1:0)%MOD;
					vl%=MOD;
				}
				am.add(i,j,vl);
			}
		}
		ll r1=0;
		for(int i=0;i<n;i++)
		{
			r1+=am.A[0][i]*(ll) A[i]%MOD;
			r1%=MOD;
		}
		sm.init(n);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				ll vl=0;
				for(int k=0;k<2*n;k++)
				{
					vl+=mt[0].A[i+n][k]*(k%n==j?1:0)%MOD;
					vl%=MOD;
				}
				sm.add(i,j,vl);
			}
		}
		ll r2=0;
		for(int i=0;i<n;i++)
		{
			r2+=sm.A[0][i]*(ll) A[i]%MOD;
			r2%=MOD;
		}
		printf("%lld %lld\n",r1,(r1+r2+MOD-A[0])%MOD);
	}
	return 0;
}
0