poj-3734(矩阵快速幂+推导)

妖狐艹你老母 2022-06-09 04:26 226阅读 0赞

问题描述:

Panda has received an assignment of painting a line of blocks. Since Panda is such an intelligent boy, he starts to think of a math problem of painting. Suppose there are N blocks in a line and each block can be paint red, blue, green or yellow. For some myterious reasons, Panda want both the number of red blocks and green blocks to be even numbers. Under such conditions, Panda wants to know the number of different ways to paint these blocks.

Input

The first line of the input contains an integer T(1≤T≤100), the number of test cases. Each of the next T lines contains an integer N(1≤N≤10^9) indicating the number of blocks.

Output

For each test cases, output the number of ways to paint the blocks in a single line. Since the answer may be quite large, you have to module it by 10007.

Sample Input

2
    1
    2

Sample Output

2
    6

题目题意:题目给我们四种颜色（红，绿，蓝，黄），总共有N块板子，我们要用那四种颜色，来涂板子，要求红色和绿色的板子必须是偶数个（可以为0）问有多少种涂色的方法?

题目分析:当时做的时候，也是想在过程上找到突破，但是想了半天也没什么好的思路，后来，我们在结果上找突破，被我旁边的大神看出了规律；

f(n)=4\*f(n-1)-2^(n-1);

这个规律是直接在答案上构造的，有一定的巧合性.

我们构造如下矩阵:

4  0  -4           f(n-1)          f(n)

0  4  -2  \*        f(n-2)  =     f(n-1)

0  0   2            1                 2

这个矩阵构造的很特殊，可能你会发现，这个不一定成立（的确，这个矩阵只符合n为3时),但是矩阵的最后一行就是控制2^(n-1) 这个变量的，所以矩阵也在改变，符合每一个n

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    const int mod=10007;
    struct matrix
    {
        int f[4][4];
        matrix operator * ( matrix &a) {
            matrix res;
            for (int i=1;i<=3;i++) {
                for (int j=1;j<=3;j++) {
                    res.f[i][j]=0;
                    for (int k=1;k<=3;k++)
                        res.f[i][j]+=(f[i][k]*a.f[k][j])%mod;
                    res.f[i][j]=(res.f[i][j]%mod+mod)%mod;//防止负数了
                }
            }
            return res;
        }
    }a,b;
    
    void init()
    {
        b.f[1][1]=4,b.f[1][3]=-4;
        b.f[2][2]=4,b.f[2][3]=-2;
        b.f[3][3]=2;
        a.f[1][1]=6,a.f[2][1]=2,a.f[3][1]=1;
    }
    
    matrix fast_pow(matrix base,int k)
    {
        matrix ans=b;
        while (k) {
            if (k&1)
              ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            int n;
            scanf("%d",&n);
            if (n==1) { printf("%d\n",2); continue;}
            if (n==2) { printf("%d\n",6); continue;}
            init();
            n-=3;
            matrix cur,ans;
            cur=b;
            cur=fast_pow(cur,n);
            ans=cur*a;
            printf("%d\n",ans.f[1][1]%mod);
        }
        return 0;
    }