Lucky Coins Sequence

柔光的暖阳◎ 2021-12-24 17:23 179阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Lucky Coins Sequence</h1> </td> 
  </tr> 
  <tr> 
   <td>Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)</td> 
  </tr> 
  <tr> 
   <td>Total Submission(s): 35 Accepted Submission(s): 29</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Problem Description 
    </div> 
    <div>
      As we all know,every coin has two sides,with one side facing up and another side facing down.Now,We consider two coins's state is same if they both facing up or down.If we have N coins and put them in a line,all of us know that it will be 2^N different ways.We call a "N coins sequence" as a Lucky Coins Sequence only if there exists more than two continuous coins's state are same.How many different Lucky Coins Sequences exist? 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Input 
    </div> 
    <div>
      There will be sevaral test cases.For each test case,the first line is only a positive integer n,which means n coins put in a line.Also,n not exceed 10^9. 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Output 
    </div> 
    <div>
      You should output the ways of lucky coins sequences exist with n coins ,but the answer will be very large,so you just output the answer module 10007. 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Input 
    </div> 
    <div> 
     <pre>3
4</pre> 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Output 
    </div> 
    <div> 
     <pre>2
6</pre> 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Source 
    </div> 
    <div>
      2010 ACM-ICPC Multi-University Training Contest（9）——Host by HNU 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Recommend 
    </div> 
    <div>
      zhengfeng 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

/*
    题意：定义一个硬币序列，如果超过三个相邻的硬币的正反相同，那么这个序列就是Lucky序列，给出序列
        长度n，问有几种Lucky序列
    
    初步思路：这种题型一般都是递推过来的，不管了先打表试一下
        打表结果：（从3开始的）
            2
            6
            16
            38
            86
            188
            402
            846
            1760
            3630
            7438
            15164
            30794
            62342
            125904
            253782
            510758
            1026684
        每项和前项的二倍差的数刚好是一个变形的斐波那契数列。
        得到递推公式：G(n)=2*(G(n-1)+F(n-2));
    #感悟：一边AC爽
    */
    #include<bits/stdc++.h>
    #define mod 10007
    using namespace std;
    /********************************矩阵模板**********************************/
    class Matrix {
        public:
            int a[3][3]; 
    
            void init(int x) {
                memset(a,0,sizeof(a));
                if(x==1){
                    a[0][0]=2;
                    a[0][1]=1;
                    a[0][2]=1;
                }else{
                    a[0][0]=2;
                    a[1][0]=2;
                    a[1][1]=1;
                    a[1][2]=1;
                    a[2][1]=1;
                }
            }
    
            Matrix operator +(Matrix b) {
                Matrix c;
                for (int i = 0; i < 3; i++)
                    for (int j = 0; j < 3; j++)
                        c.a[i][j] = (a[i][j] + b.a[i][j]) % mod;
                return c;
            }
    
            Matrix operator +(int x) {
                Matrix c = *this;
                for (int i = 0; i < 3; i++)
                    c.a[i][i] += x;
                return c;
            }
    
            Matrix operator *(Matrix b)
            {
                Matrix p;
                memset(p.a,0,sizeof p.a);
                for (int i = 0; i < 3; i++)
                    for (int j = 0; j < 3; j++)
                    for (int k = 0; k < 3; k++)
                        p.a[i][j] = (p.a[i][j] + (a[i][k]*b.a[k][j])%mod) % mod;
                return p;
            }
    
            Matrix power_1(int t) {
                Matrix ans,p = *this;
                memset(ans.a,0,sizeof ans.a);
                for(int i=0;i<3;i++) ans.a[i][i]=1;
                while (t) {
                    if (t & 1)
                        ans=ans*p;
                    p = p*p;
                    t >>= 1;
                }
                return ans;
            }
            
            Matrix power_2(Matrix a,Matrix b,int x){
                while(x){
                    if(x&1){
                        b=a*b;
                    }
                    a=a*a;
                    x>>=1;
                }
                return b;
            }
    }unit,init;
    /********************************矩阵模板**********************************/
    int n;
    int main(){
        // freopen("in.txt","r",stdin);
        while(scanf("%d",&n)!=EOF){
            if(n<3){
                printf("0\n");
                continue;
            }
            if(n==3){
                printf("2\n");
                continue;
            }
            unit.init(1);
            init.init(0);
            // for(int i=0;i<3;i++){
                // for(int j=0;j<3;j++){
                    // cout<<unit.a[i][j]<<" ";
                // }
                // cout<<endl;
            // }
            init=init.power_1(n-3);
            printf("%d\n",(unit*init).a[0][0]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wuwangchuxin0924/p/6388559.html