POJ2118基础矩阵快速幂

题意：

an=Σ1<=i<=kan-ibi mod 10 000 for n >= k，题意看了好久才懂，有点蛋疼啊，

这个题目要是能看懂题意就简单了，先给你k,然后给你a0 a1 a2 a3 ..ak-1.

然后给你b1 b2 b3 b4 ..bk,然后给你一个i，让你输出ai的值，如果i < k直接输出输入时的ai就行，否则就按照他给的那个公式

an=Σ1<=i<=kan-ibi mod 10 000 for n >= k

比如k=3

那么 a3 = a2*b1 + a1*b2 + a0*b3

a4 = a3*b1 + a2*b2 + a1*b3

a5 = a4*b1 + a3*b2 + a2*b3

a6 = a5*b1 + a4*b2 + a3*b3

......

下面构造矩阵，这个矩阵是k*k的，也就是每次都是变的，但是有规律，最大是100*100

，拿k=3举例子

a3 a2 a1 0 0 b1 a2 a3 a4

1 0 b2

0 1 b3

这样就轻松构造这个矩阵了吧，要是k=4也一样

0 0 0 b1

1 0 0 b2

0 1 0 b3

0 0 1 b4

....

好啦就说这么多，最近在忙活写服务器玩，去写自己的服务器喽......

#include<stdio.h>

#include<string.h>

#define MOD 10000

typedef struct

{

    int mat[110][110];

}M;

M matM(M a ,M b ,int n)

{

    M c;

    memset(c.mat ,0 ,sizeof(c.mat));

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

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

    if(a.mat[i][k])

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

    c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;

    return c;

}

M qPowMat(M a ,int b ,int n)

{

    M c;

    memset(c.mat ,0 ,sizeof(c.mat));

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

    c.mat[i][i] = 1;

    while(b)

    {

        if(b & 1) c = matM(c ,a ,n);

        a = matM(a ,a ,n);

        b >>= 1;

    }

    return c;

}

int main ()

{

    int k ,n ,i ,j;

    int A[105] ,B[105];

    M star ,ans;

    while(~scanf("%d" ,&k) && k)

    {

        for(i = 0 ;i < k ;i ++)

        scanf("%d" ,&A[i]);

        for(i = k ;i >= 1 ;i --)

        scanf("%d" ,&B[i]);

        scanf("%d" ,&n);

        if(n < k)

        {

            printf("%d\n" ,A[n]);

            continue;

        }

        memset(star.mat ,0 ,sizeof(star.mat));

        for(i = 1 ;i < k ;i ++)

        star.mat[i+1][i] = 1;

        for(i = 1 ;i <= k ;i ++)

        star.mat[i][k] = B[i];

        ans = qPowMat(star ,n - k + 1 ,k);

        int sum = 0;

        for(i = 1 ;i <= k ;i ++)

        sum = (sum + A[i-1] * ans.mat[i][k]) % MOD;

        printf("%d\n" ,sum);

    }

    return 0;

}

巴特西

POJ2118基础矩阵快速幂

最新文章

热门文章