hdu 3483 矩阵乘法

这个题目上周对抗赛题目，搞了我好久对数学这种不是很敏感

其实都不是自己想出来的，看其他的资料和博客的推导还是有点难度的，反正我是推不出来

通过二项式定理的化简

有两个博客写得比较好

http://972169909-qq-com.iteye.com/blog/1863402

http://www.cppblog.com/Yuan/archive/2010/08/13/123268.html

反正构造好二项式之后，乘N次，就可以得到结果了，因为右边的式子初始全部是x。

#include <iostream>

#include <cstring>

#include <cstdio>

#define ll __int64

using namespace std;

const int maxn = ;

ll c[maxn][maxn], a[maxn][maxn], b[maxn][maxn], t[maxn][maxn];

ll  N,x,M;

void init()

{

    int i, j;

    memset(c, , sizeof(c));

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

    {

        c[i][] = c[i][i] = ;

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

        {

            c[i][j] = (c[i-][j] + c[i-][j-]) % M;

        }

    }

    memset(a, , sizeof(a));

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

    {

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

        {

            a[i][j] = (c[i][j] * x) % M;

        }

    }

    memcpy(a[x+], a[x], sizeof(a[x]));

    a[x+][x+] = ;

    memset(b, , sizeof(b));

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

    {

        b[i][i] = ;

    }

}

void mul(long long p[maxn][maxn], long long q[maxn][maxn])

{

    int i, j, k;

    memset(t, , sizeof(t));

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

    {

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

        {

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

            {

                t[i][j] = (t[i][j] + p[i][k] * q[k][j]) % M;

            }

        }

    }

    memcpy(q, t, sizeof(t));

}

void cal()

{

    while (N)

    {

        if (N & )

        {

            mul(a, b);

        }

        mul(a, a);

        N >>= ;

    }

}

int main()

{

    while (scanf("%I64d %I64d %I64d", &N, &x,&M)&& N> && x> &&M>)

    {

        init();

        cal();

        printf("%I64d\n", b[x+][]);

    }

    return ;

}

巴特西

hdu 3483 矩阵乘法

最新文章

热门文章