結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー takayuta1999takayuta1999
提出日時 2015-04-26 23:22:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 2,846 bytes
コンパイル時間 1,183 ms
コンパイル使用メモリ 46,748 KB
実行使用メモリ 9,224 KB
最終ジャッジ日時 2023-09-18 09:57:25
合計ジャッジ時間 2,599 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,936 KB
testcase_01 AC 2 ms
4,936 KB
testcase_02 AC 40 ms
9,204 KB
testcase_03 AC 5 ms
9,176 KB
testcase_04 AC 15 ms
9,092 KB
testcase_05 AC 13 ms
9,224 KB
testcase_06 AC 16 ms
9,204 KB
testcase_07 AC 25 ms
9,192 KB
testcase_08 AC 5 ms
9,140 KB
testcase_09 AC 20 ms
9,172 KB
testcase_10 AC 9 ms
9,120 KB
testcase_11 AC 9 ms
9,148 KB
testcase_12 AC 14 ms
9,144 KB
testcase_13 AC 7 ms
9,072 KB
testcase_14 AC 3 ms
9,168 KB
testcase_15 AC 30 ms
9,212 KB
testcase_16 AC 26 ms
9,196 KB
testcase_17 AC 8 ms
9,060 KB
testcase_18 AC 28 ms
9,224 KB
testcase_19 AC 39 ms
9,212 KB
testcase_20 AC 13 ms
7,052 KB
testcase_21 AC 14 ms
7,068 KB
testcase_22 AC 13 ms
7,052 KB
testcase_23 AC 3 ms
5,128 KB
testcase_24 AC 9 ms
6,868 KB
testcase_25 AC 7 ms
6,680 KB
testcase_26 AC 8 ms
6,628 KB
testcase_27 AC 9 ms
6,976 KB
testcase_28 AC 3 ms
5,484 KB
testcase_29 AC 12 ms
7,024 KB
testcase_30 AC 40 ms
9,084 KB
testcase_31 AC 3 ms
9,128 KB
testcase_32 AC 13 ms
9,176 KB
testcase_33 AC 18 ms
9,208 KB
testcase_34 AC 14 ms
9,192 KB
testcase_35 AC 13 ms
9,184 KB
testcase_36 AC 29 ms
9,144 KB
testcase_37 AC 4 ms
9,148 KB
testcase_38 AC 32 ms
9,156 KB
testcase_39 AC 13 ms
9,184 KB
権限があれば一括ダウンロードができます

ソースコード

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