Array Challenge

2024-03-03 04:58

文章标签 array challenge

本文主要是介绍Array Challenge，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Array Challenge

Problem Description

There’s an array that is generated by following rule.

h 0 =2,h 1 =3,h 2 =6,h n =4h n−1 +17h n−2 −12h n−3 −16
And let us define two arrays

b n anda n as below.

b n =3h n+1 h n +9h n+1 h n−1 +9h 2 n +27h n h n−1 −18h n+1 −126h n −81h n−1 +192(n>0)

a n =b n +4 n
Now, you have to print

⌊√(a n )⌋ , n>1.
Your answer could be very large so print the answer modular 1000000007.

Input

The first line of input contains T (1 <= T <= 1000) , the number of test cases.
Each test case contains one integer n (1 < n <=

10 15 ) in one line.

Output

For each test case print ⌊√(a_n )⌋ modular 1000000007.

Sample Input

Sample Output

1255
324725
13185773

看起来非常难。

试着用程序列出了一下h和a的前几个数然后就发现h的公式稍微改一下就是a的公式，稍微有个坑，算an的值直接取模的话会有负数的情况，所以先加上mod再取模就可以了。

h n =4h n−1 +17h n−2 −12h n−3 −16

a n =4a n−1 +17a n−2 −12a n−3

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define mod 1000000007
//http://acm.split.hdu.edu.cn/diy/contest_show.php?cid=32494
using namespace std;
typedef long long ll;struct matrix{int row,col;ll A[20][20];matrix(int Row=0,int Col=0){memset(A,0,sizeof(A));row=Row;col=Col;}
};matrix operator *(matrix a,matrix b){matrix c(a.row,b.col);for(int i=0;i<a.row;i++)for(int j=0;j<b.col;j++)for(int k=0;k<a.col;k++)c.A[i][j]=(c.A[i][j]+a.A[i][k]*b.A[k][j]+mod)%mod;return c;
}matrix matrix_pow(matrix a,ll n){matrix ans(a.row,a.col);for(int i=0;i<a.row;i++)ans.A[i][i]=1;while(n){if(n%2)ans=a*ans;a=a*a;n/=2;}return ans;
}int main()
{ll n,T;matrix a(3,3);a.A[0][0]=4;a.A[0][1]=17;a.A[0][2]=-12;a.A[1][0]=1;a.A[1][1]=0;a.A[1][2]=0;a.A[2][0]=0;a.A[2][1]=1;a.A[2][2]=0;matrix x1(3,3),xn(3,3);x1.A[0][0]=1255;x1.A[1][0]=197;x1.A[2][0]=31;scanf("%lld",&T);while(T--){scanf("%lld",&n);xn=matrix_pow(a,n-2)*x1;printf("%lld\n",xn.A[2][0]);}return 0;}

这篇关于Array Challenge的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！