Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ctrl-alt-defeat-2019 Hosoyev indeks C++ 100/100OK 24. apr '19 @ 20:10

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 50/50 3,223 MiB 0,004 s OK
#2 [več] 50/50 3,223 MiB 0,004 s OK

Ocenjevani program (Index.cpp):
#include <bits/stdc++.h>

using namespace std;
const long long mod=1000000007;

int c[5][5]={{1,1,0,1,1},{1,1,0,0,0},{0,0,1,0,0},{1,0,0,1,0},{1,0,0,0,0}};
long long v[55][5][5];
long long a[5][5]={{2,1,2,0,0},{0,0,0,2,1},{2,1,2,0,0},{1,1,1,0,0},{0,0,0,1,1}};

void ini()
{
	memcpy(v[0],a,sizeof a);
	for(int o=1;o<55;o++)
	{
		for(int d=0;d<5;d++)
		{
			for(int e=0;e<5;e++)
			{
				long long sum=0;
				for(int i=0;i<5;i++)
				{
					for(int j=0;j<5;j++)
					{
						if(c[i][j]==1)
						{
							sum+=(v[o-1][d][i]*v[o-1][j][e])%mod;
							if(sum>=mod) sum%=mod;
						}
					}
				}
				v[o][d][e]=sum;
			}
		}
	}
}


int main()
{
	ini();
	int t;
	scanf("%d",&t);
	while(t--)
	{
		long long n;
		scanf("%lld",&n);
		long long res[5][5];
		bool first=0;
		int ex=0;
		while(n)
		{
			if(n&1)
			{
				if(first==0)
				{
					memcpy(res,v[ex],sizeof v[ex]);
					first=1;
				}
				else
				{
					long long int temp[5][5];
					for(int d=0;d<5;d++)
					{
						for(int e=0;e<5;e++)
						{
							long long sum=0;
							for(int i=0;i<5;i++)
							{
								for(int j=0;j<5;j++)
								{
									if(c[i][j]==1)
									{
										sum+=(res[d][i]*v[ex][j][e])%mod;
										if(sum>=mod) sum%=mod;
									}
								}
							}
							temp[d][e]=sum;
						}
					}
					memcpy(res,temp,sizeof(temp));
				}
			}
			ex++;
			n/=2;
		}
		long long a=0;
		for(int i=0;i<5;i++)
		{
			for(int j=0;j<5;j++)
			{
				a+=res[i][j];
				if(a>=mod) a%=mod;
			}
		}
		printf("%lld\n",a);
	}
	return 0;
}