LightOJ 1132 Summing up Powers

题目在这里>_<

题意

给你$N$和$K$，求$(1^K + 2^K + 3^K + \dots + N^K) \pmod {2^{32}}$

思路

因为$(n+1)^k=C_k^0 n^0+C_k^1 n^1 + \cdots + C_k^k n^k$
所以可以得到转移矩阵：
$$
\begin{bmatrix}
1 & 1 & 0 & 0 & \cdots & 0 \\\\
0 & C_k^k & C_k^{k-1} & C_k^{k-2} & \cdots &C_k^0 \\\\
0 & 0 & C_{k-1}^{k-1} & C_{k-1}^{k-2} & \cdots & C_{k-1}^0 \\\\
\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\\\
0 & 0 & 0 & 0 &\cdots &1
\end{bmatrix}
\begin{bmatrix}
S_{n-1} \\\\
n^k \\\\
n^{k-1} \\\\
n^{k-2} \\\\
\vdots \\\\
n^0
\end{bmatrix}
=
\begin{bmatrix}
S_n \\\\
(n+1)^k \\\\
(n+1)^{k-1} \\\\
(n+1)^{k-2} \\\\
\vdots \\\\
(n+1)^0
\end{bmatrix}
$$
这是一个$(k+2)*(k+2)$的转移矩阵，由此构造即可求得答案。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=100;
typedef unsigned long long ll;
const ll mod=(1LLu<<32);
struct Matrix
{
    int n,m;
    ll map[Nmax][Nmax];
    Matrix(int x,int y)
    {
        n=x;m=y;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                map[i][j]=0LLu;
    }
    Matrix operator * (const Matrix b)
    {
        Matrix c(n,b.m);
        if(m==b.n)
        {
            for(int i=1;i<=c.n;i++)
                for(int k=1;k<=m;k++)
                    for(int j=1;j<=c.m;j++)
                        c.map[i][j]=(c.map[i][j]+(map[i][k]*b.map[k][j])%mod)%mod;
            return c;
        }
        printf("error!!!!!!!!!!!!!!\n");   
        return c;
    }
    Matrix operator + (const Matrix b)
    {
        Matrix c(n,m);
        if(m==b.m && n==b.n)
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    c.map[i][j]=(map[i][j]+b.map[i][j])%mod;
            return c;
        }
        printf("error!!!!!!!!!!!!!!\n");   
        return c;
    }
    void show()
    {
        printf("n:%d m:%d\n",n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%4llu%c",map[i][j],j==m?'\n':' ');
    }
};
ll n,k;

ll C[Nmax][Nmax];
ll work()
{
    Matrix base(k+2,k+2);
    base.map[1][1]=base.map[1][2]=1LLu;
    for(int i=2;i<=(int)k+2;i++)
        for(int j=i;j<=(int)k+2;j++)
            base.map[i][j]=C[k+2-i][k+2-j];
    //base.show();
    Matrix ans(k+2,k+2);
    for(int i=1;i<=(int)k+2;i++)
        ans.map[i][i]=1LLu;
    if(n==1)
        return 1LLu;
    ll t=n-1LLu;
    while(t)
    {
        if(t&1)
            ans=ans*base;
        base=base*base;
        t>>=1;
    }
    //cout<<"ans:\n";
    //ans.show();
    //base.show();
    Matrix now(k+2,1);
    now.map[1][1]=1LLu;
    for(int i=2;i<=(int)k+2;i++)
        now.map[i][1]=1LLu<<((int)k+2-i);
    //now.show();
    ans=ans*now;
    //ans.show();
    //now.show();
    //printf("\n\n\n");
    return ans.map[1][1];
}
void init()
{
   C[0][0]=1LLu;
   C[1][0]=C[1][1]=1LLu;
   for(int i=2;i<=50;i++)
   {
       for(int j=0;j<=i;j++)
       {
            if(j==0)
                C[i][j]=1LLu;
            else 
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
       }
   }
   //for(int i=0;i<=10;i++)
   //{
       //for(int j=0;j<=i;j++)
           //printf("%4llu%c",c[i][j],j==i?'\n':' ');
   //}
}
int main()
{
    #ifdef test
    #endif
    //freopen("d.in","r",stdin);
    int t;
    init();
    scanf("%d",&t);
    t=0;
    while(~scanf("%llu%llu",&n,&k))
    {
        t++;
        printf("Case %d: %llu\n",t,work());
    }
    return 0;
}