【hdu 6172】Array Challenge（数列、找规律）-白红宇

【hdu 6172】Array Challenge（数列、找规律）

阅读量：7089 次

发布时间：2019-06-28

本文共 2696 字，大约阅读时间需要 8 分钟。

题意

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 bnandan as below.

b_n=3h_{n+1} h_n+9h_{n+1} h_{n-1}+9h_n^2+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 \(\left \lfloor \sqrt{a_n} \right \rfloor\) , n>1.

Your answer could be very large so print the answer modular 1000000007.

题解

首先要打表，然后就可以：

方法1，找规律：

令\(f_n=\left \lfloor \sqrt{a_n} \right \rfloor\)，打表出来，发现接近7倍关系，再打出 \(7f_{n-1}-f_{n}\)，会发现是\(f_{n-2}\)的4倍，所以\(f_n=7f_{n-1}-4f_{n-2}\)。再用矩阵快速幂。注意取模有负数。

方法2，猜：

前几项和h的前几项差不多，于是模仿h的递推式，\(f_n=4f_{n-1}+17f_{n-2}-12f_{n-3}\)，刚好符合。

方法3，BM算法：

如果递推式是线性的，就把前几项带进去就可以得到递推式。

具体算法介绍建议看这个：、

方法4，数学递推，我不会。

代码

#include 
    
     #include 
     #include 
      
       #include 
       
        using namespace std;#define mem(a,b) memset(a,b,sizeof(a))#define rep(i,l,r) for (int i=l;i
        
         vis;struct Sta{    int a[6][6],step,x,y;    Sta(){step=x=y=0;}};int gujia(Sta s){    int ans=0;    rep(i,0,6)rep(j,0,i+1)    if(s.a[i][j])ans+=abs(s.a[i][j]-i);    return ans;}ull haxi(Sta s){    ull ans=0;    rep(i,0,6)rep(j,0,i+1){        ans<<=3;ans|=s.a[i][j];    }    return ans;}int bfs(Sta s){    vis.clear();    queue
         
          q;q.push(s); while(!q.empty()){ Sta now=q.front();q.pop(); if(gujia(now)==0)return now.step; rep(i,0,4){ int x=now.x,y=now.y; int nx=x+dx[i],ny=y+dy[i]; if(nx>=0 && nx<6 && ny>=0 && ny<=nx){ swap(now.a[x][y],now.a[nx][ny]); now.x=nx,now.y=ny,++now.step; ull hx=haxi(now); if(!vis[hx]&&gujia(now)+now.step<21){ q.push(now); vis[hx]=true; } swap(now.a[x][y],now.a[nx][ny]); now.x-=dx[i],now.y-=dy[i],--now.step; } } } return -1;}int main() { int t; scanf("%d",&t); while(t--){ Sta s; rep(i,0,6) rep(j,0,i+1){ scanf("%d",&s.a[i][j]); if(s.a[i][j]==0)s.x=i,s.y=j; } int ans=bfs(s); if(ans==-1)puts("too difficult");else printf("%d\n",ans); } return 0;}

#include 
    
     #include 
     
      #include 
      
       using namespace std;#define rep(i,a,n) for (int i=a;i

VI;typedef long long ll;const ll mod=1000000007;ll qpow(ll a,ll b) {ll res=1;for(a%=mod;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;return res;}VI BM(VI s) {//c[0]s[0]+c[1]s[1]+...=0 VI C(1,1),B(1,1); int L=0,m=1,rev=1; rep(n,0,SZ(s)) { ll d=0; rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod; if (d==0) ++m; else if (2*L<=n) { VI T=C; ll c=mod-d*rev%mod; C.resize(SZ(B)+m); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; L=n+1-L; B=T; rev=qpow(d,mod-2); m=1; } else { ll c=mod-d*rev%mod; C.resize(SZ(B)+m); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; ++m; } } rep(i,0,SZ(C))printf("%dx[%d]%s",C[i],i,i+1==SZ(C)?"=0\n":"+"); return C;}调用：BM(VI{31,197,1255,7997})

转载地址：http://ejfql.baihongyu.com/

你可能感兴趣的文章