hdu 3483 矩阵乘法-白红宇

hdu 3483 矩阵乘法

阅读量：5297 次

发布时间：2019-06-14

本文共 1674 字，大约阅读时间需要 5 分钟。

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

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

通过二项式定理的化简

有两个博客写得比较好

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

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

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

#include 
     
      #include 
      
       #include 
       
        #define ll __int64using namespace std;const int maxn = 52;ll c[maxn][maxn], a[maxn][maxn], b[maxn][maxn], t[maxn][maxn];ll  N,x,M;void init(){    int i, j;    memset(c, 0, sizeof(c));    for (i = 0; i <= x; i++)    {        c[i][0] = c[i][i] = 1;        for (j = 1; j < i; j++)        {            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % M;        }    }    memset(a, 0, sizeof(a));    for (i = 0; i <= x; i++)    {        for (j = 0; j <= i; j++)        {            a[i][j] = (c[i][j] * x) % M;        }    }    memcpy(a[x+1], a[x], sizeof(a[x]));    a[x+1][x+1] = 1;    memset(b, 0, sizeof(b));    for (i = 0; i <= x+1; i++)    {        b[i][i] = 1;    }}void mul(long long p[maxn][maxn], long long q[maxn][maxn]){    int i, j, k;    memset(t, 0, sizeof(t));    for (i = 0; i <= x+1; i++)    {        for (j = 0; j <= x+1; j++)        {            for (k = 0; k <= x+1; 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 & 1)        {            mul(a, b);        }        mul(a, a);        N >>= 1;    }}int main(){    while (scanf("%I64d %I64d %I64d", &N, &x,&M)&& N>0 && x>0 &&M>0)    {        init();        cal();        printf("%I64d\n", b[x+1][0]);    }    return 0;}