LightOJ 1132 Summing up Powers：矩阵快速幂 + 二项式定理

题目链接：http://lightoj.com/volume_showproblem.php?problem=1132

题意：

　　给定n、k，求(1^K + 2^K + 3^K + ... + N^K) % 2³²。

题解：

　　设sum(i) = 1^K + 2^K + 3^K + ... + i^K

　　所以要从sum(1)一直推到sum(n)。

　　所以要找出sum(i)和sum(i+1)之间的关系：

　　好了可以造矩阵了。

　　（n = 6时）

　　矩阵表示（大小为 1 * (k+2)）：

　　初始矩阵start：

　　也就是：

　　特殊矩阵special：

AC Code:

#include <iostream>

#include <stdio.h>

#include <string.h>

#define MAX_L 60

#define MAX_K 55

using namespace std;

struct Mat

{

    int n;

    int m;

    unsigned val[MAX_L][MAX_L];

    Mat()

    {

        n=;

        m=;

        memset(val,,sizeof(val));

    }

    void print_mat()

    {

        cout<<"--------"<<endl;

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

        {

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

            {

                cout<<val[i][j]<<" ";

            }

            cout<<endl;

        }

        cout<<"--------"<<endl;

    }

};

int k,t;

long long n;

unsigned c[MAX_K][MAX_K];

void cal_combination()

{

    memset(c,,sizeof(c));

    c[][]=;

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

    {

        c[i][]=;

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

        {

            c[i][j]=c[i-][j]+c[i-][j-];

        }

    }

}

Mat make_unit(int n)

{

    Mat mat;

    mat.n=n;

    mat.m=n;

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

    {

        mat.val[i][i]=;

    }

    return mat;

}

Mat make_start(int k)

{

    Mat mat;

    mat.n=;

    mat.m=k+;

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

    {

        mat.val[][i]=;

    }

    return mat;

}

Mat make_special(int k)

{

    Mat mat;

    mat.n=k+;

    mat.m=k+;

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

    {

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

        {

            mat.val[i][j]=c[k-j+][i-j];

        }

    }

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

    {

        mat.val[i][]=mat.val[i][];

    }

    mat.val[][]=;

    return mat;

}

Mat mul_mat(const Mat &a,const Mat &b)

{

    Mat c;

    if(a.m!=b.n)

    {

        cout<<"Error: mul_mat"<<endl;

        return c;

    }

    c.n=a.n;

    c.m=b.m;

    for(int i=;i<a.n;i++)

    {

        for(int j=;j<b.m;j++)

        {

            for(int k=;k<a.m;k++)

            {

                c.val[i][j]+=a.val[i][k]*b.val[k][j];

            }

        }

    }

    return c;

}

Mat quick_pow_mat(Mat mat,long long k)

{

    Mat ans;

    if(mat.n!=mat.m)

    {

        cout<<"Error: quick_pow_mat"<<endl;

        return ans;

    }

    ans=make_unit(mat.n);

    while(k)

    {

        if(k&)

        {

            ans=mul_mat(ans,mat);

        }

        mat=mul_mat(mat,mat);

        k>>=;

    }

    return ans;

}

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    cal_combination();

    cin>>t;

    for(int cas=;cas<=t;cas++)

    {

        cin>>n>>k;

        Mat start=make_start(k);

        Mat special=make_special(k);

        Mat ans=mul_mat(start,quick_pow_mat(special,n-));

        cout<<"Case "<<cas<<": "<<ans.val[][]<<endl;

    }

}

巴特西

LightOJ 1132 Summing up Powers：矩阵快速幂 + 二项式定理

最新文章

热门文章