fzu2198 快来快来数一数-白红宇

fzu2198 快来快来数一数

阅读量：5040 次

发布时间：2019-06-12

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

Accept: 204 Submit: 627
Time Limit: 1000 mSec Memory Limit : 65536 KB

Problem Description

n个六边形排成一行，相邻两个六边形共用一条边，如下图所示：

记这个图形的生成树个数为t(n)（由于每条边都是不同的，不存在同构的问题）。那么t(1)=6，t(2)=35……

给出n，求mod 1000000007

Input

第一行给出数据组数T。

之后每一行给出一个正整数n。

T大约为50000，n<=10^18。

Output

每组数据输出一行答案。

Sample Input

      2212345678987654321 

Sample Output

41733521876

Source

这题用矩阵快速幂做，先用dp[i][f]表示处理到第i个矩形，第i个矩形右边那条边会不会不去掉的方案数，那么dp[i][1]=d[i-1][0]+dp[i-1][1],dp[i][0]=4*dp[i-1][1]+5*dp[i-1][0].

我们可以构造矩阵【dp[i][1],dp[i][0],sum[i] 】*A=【dp[i+1][1],dp[i+1][0],sum[i+1] 】.

1 4 5

容易求出A=1 5 6

0 0 1

然后用矩阵快速幂就行了，这里要注意，这题卡常数，所以要先初始化64个矩阵的乘方，然后再算，而且注意取模不能取太多，不然会超时。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;typedef unsigned long long ll;#define inf 0x7fffffff#define pi acos(-1.0)#define MOD 1000000007struct matrix{ int n,m,i; ll data[3][3];}a,b,c,d[99],t;matrix multi(matrix &a,matrix &b){ matrix ans; memset(ans.data,0,sizeof(ans.data)); ans.data[0][0]=(ans.data[0][0]+a.data[0][0]*b.data[0][0]); ans.data[0][1]=(ans.data[0][1]+a.data[0][0]*b.data[0][1]); ans.data[0][2]=(ans.data[0][2]+a.data[0][0]*b.data[0][2]); ans.data[0][0]=(ans.data[0][0]+a.data[0][1]*b.data[1][0]); ans.data[0][1]=(ans.data[0][1]+a.data[0][1]*b.data[1][1]); ans.data[0][2]=(ans.data[0][2]+a.data[0][1]*b.data[1][2]); ans.data[0][0]=(ans.data[0][0]+a.data[0][2]*b.data[2][0])%MOD; ans.data[0][1]=(ans.data[0][1]+a.data[0][2]*b.data[2][1])%MOD; ans.data[0][2]=(ans.data[0][2]+a.data[0][2]*b.data[2][2])%MOD; ans.data[1][0]=(ans.data[1][0]+a.data[1][0]*b.data[0][0]); ans.data[1][1]=(ans.data[1][1]+a.data[1][0]*b.data[0][1]); ans.data[1][2]=(ans.data[1][2]+a.data[1][0]*b.data[0][2]); ans.data[1][0]=(ans.data[1][0]+a.data[1][1]*b.data[1][0]); ans.data[1][1]=(ans.data[1][1]+a.data[1][1]*b.data[1][1]); ans.data[1][2]=(ans.data[1][2]+a.data[1][1]*b.data[1][2]); ans.data[1][0]=(ans.data[1][0]+a.data[1][2]*b.data[2][0])%MOD; ans.data[1][1]=(ans.data[1][1]+a.data[1][2]*b.data[2][1])%MOD; ans.data[1][2]=(ans.data[1][2]+a.data[1][2]*b.data[2][2])%MOD; ans.data[2][0]=(ans.data[2][0]+a.data[2][0]*b.data[0][0]); ans.data[2][1]=(ans.data[2][1]+a.data[2][0]*b.data[0][1]); ans.data[2][2]=(ans.data[2][2]+a.data[2][0]*b.data[0][2]); ans.data[2][0]=(ans.data[2][0]+a.data[2][1]*b.data[1][0]); ans.data[2][1]=(ans.data[2][1]+a.data[2][1]*b.data[1][1]); ans.data[2][2]=(ans.data[2][2]+a.data[2][1]*b.data[1][2]); ans.data[2][0]=(ans.data[2][0]+a.data[2][2]*b.data[2][0])%MOD; ans.data[2][1]=(ans.data[2][1]+a.data[2][2]*b.data[2][1])%MOD; ans.data[2][2]=(ans.data[2][2]+a.data[2][2]*b.data[2][2])%MOD; return ans; /* for(int i=0;i<3;i++){ for(int k=0;k<3;k++){ if(a.data[i][k]>0) for(int j=0;j<3;j++){ ans.data[i][j]=(ans.data[i][j]+a.data[i][k]*b.data[k][j])%MOD; } } } return ans; */}matrix fast_mod(ll n){ matrix ans; ans.n=3; ans.m=3; memset(ans.data,0,sizeof(ans.data)); ans.data[0][0]=ans.data[1][1]=ans.data[2][2]=1; int num=1; while(n>0){ if(n&1){ ans=multi(ans,d[num]); } num++; n>>=1; } printf("%I64d\n",(ans.data[0][2]+5*ans.data[1][2]+6*ans.data[2][2] )%MOD);}void init(){ int i,j; d[1].n=d[1].m=3; d[1].data[0][0]=1; d[1].data[0][1]=4; d[1].data[0][2]=5; d[1].data[1][0]=1; d[1].data[1][1]=5; d[1].data[1][2]=6; d[1].data[2][0]=0; d[1].data[2][1]=0; d[1].data[2][2]=1; for(i=2;i<64;i++){ d[i]=multi(d[i-1],d[i-1]); }}int main(){ ll n,m,i,j; int T; init(); scanf("%d",&T); while(T--) { scanf("%I64d",&n); if(n==0){ printf("0\n"); continue; } fast_mod(n-1); } return 0;}

转载于:https://www.cnblogs.com/herumw/p/9464606.html

你可能感兴趣的文章