Choosing number ZOJ - 3690 （矩阵快速幂）

时间：2022-05-04 21:17:21

题意：n个人站成一排，每个人任意从1——m中任意取一个数，要求相邻两个人的如果数字相同，数字要大于k。

分划思想推导表达式：

假设  i  个人时。第i个人的选择有两种一种是选择小于等于k的数，另一种是大于k的数。则设这两种情况的组合数分别为F（i）和 G(i)

那么F（i）=（m-k）（F（i-1）+G(i-1)）；m-k表示第i个人，选择了大于k的选择。

那么G(i)=kF(i-1)+(k-1)G(i-1)；  k*F（i-1），表示第i个人选的是大于k的数，而第i个人只能在0—k种选择，所以0—k都可以选择。但是，如果第i-1人选择了

0—k中的一个数，那么为了满足条件相邻元素大于k的原则，所以不能选择第i-1的数，所以是k-1;

然后就是基础的构造函数了。

#include<cstdio>

#include<cstring>

#define mod int(1e9+7)

#define ll long long

ll m, k, n;

struct jz

{

    ll num[][];

    jz(){ memset(num, , sizeof(num)); }

    jz operator*(const jz &p)const

    {

        jz ans;

        for (int k = ; k < ;++k)

        for (int i = ; i < ;++i)

        for (int j = ; j < ; ++j)

            ans.num[i][j] = (ans.num[i][j] + num[i][k] * p.num[k][j] % mod) % mod;

        return ans;

    }

}p;

jz POW(jz x, ll n)

{

    jz ans;

    for (int i = ; i < ; ++i)ans.num[i][i] = ;

    for (; n;n>>=, x=x*x)

    if (n & )ans = ans*x;

    return ans;

}

void init()

{

        p.num[][] = m - k; p.num[][] = m - k;

        p.num[][] = k; p.num[][] = k - ;

}

int main()

{

    while (scanf("%lld%lld%lld", &n, &m, &k)!=EOF)

    {

        ll G1 = k;

        ll F1 = m - k;

            init();

            jz ans = POW(p, n - );

            printf("%lld\n", (ans.num[][] * F1%mod + ans.num[][] * G1%mod+ans.num[][]*F1%mod+ans.num[][]*G1%mod) % mod);

    }

    return ;

}

相关文章