ZOJ 3690 Choosing number（矩阵快速幂）

Choosing number

---

Time Limit: 2 Seconds       Memory Limit: 65536 KB

---

There are n people standing in a row. And There are m numbers, 1.2...m. Every one should choose a number. But if two persons standing adjacent to each other choose the same number, the number shouldn't equal or less than k. Apart from this rule, there are no more limiting conditions.

And you need to calculate how many ways they can choose the numbers obeying the rule.

Input

There are multiple test cases. Each case contain a line, containing three integer n (2 ≤ n ≤ 10⁸), m (2 ≤ m ≤ 30000), k(0 ≤ k ≤ m).

Output

One line for each case. The number of ways module 1000000007.

Sample Input

4 4 1

Sample Output

216

n个人站一列，每人选择一个数从1-m，相邻两人若选择同一个数x，则x>k，求多少种选择方法。

递推：f(n)=f(n-1)*(m-1)+f(n-2)*(m-k);

转化为矩阵

A矩阵 为初始矩阵  

f1 0

f0 0

B矩阵 系数矩阵

m-1 m-k

1   0

所求结果为 矩阵ans=B^(n-1)*A  ans[0][0]

#include<stdio.h>
#include<string.h>
#define mod 1000000007
#define N 2
typedef long long LL;
struct Matrix
{
    LL mat[N][N];
};

Matrix unit_matrix =
{
    1, 0,
    0, 1,
}; //单位矩阵

Matrix mul(Matrix a, Matrix b) //矩阵相乘
{
    Matrix res;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
        {
            res.mat[i][j] = 0;
            for(int k = 0; k < N; k++)
            {
                res.mat[i][j] += a.mat[i][k] * b.mat[k][j];
                res.mat[i][j] %= mod;
            }
        }
    return res;
}

Matrix pow_matrix(Matrix a, LL n)  //矩阵快速幂
{
    Matrix res = unit_matrix;
    while(n != 0)
    {
        if(n & 1)
            res = mul(res, a);
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

int main()
{
    int n,m,k,T;
    Matrix tmp, arr;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        if(n == 0)
            printf("1\n");
        if(n == 1)
            printf("%d\n",m);
        else
        {
            memset(arr.mat, 0, sizeof(arr.mat));
            memset(tmp.mat,0,sizeof(tmp.mat));
            tmp.mat[0][0]=m-1;
            tmp.mat[0][1]=m-k;//系数矩阵
            tmp.mat[1][0]=1;
            arr.mat[0][0]=m;//初始矩阵
            arr.mat[1][0]=1;
            Matrix p = pow_matrix(tmp, n-1);//系数矩阵的n-1次方乘上初始矩阵
            p = mul(p, arr);
            LL ans = (p.mat[0][0] + mod) % mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}