lightoj1132—Summing up Powers （取膜技巧&&组合数应用）

题目链接：https://vjudge.net/problem/LightOJ-1132

题目意思：(1^K + 2^K + 3^K + ... + N^K) % 2³²

矩阵快速幂的题目一般都很短，这道题也一样就是这么简单。

思路：运用到了组合数a^k=C(k,0)*a^k+C(k,1)*a^(k-1)+C(k,2)*a^(k-2)+C(k,3)*a^(k-3)+C(k,4)*a^(k-4)+……C(k,k)*a^(k-k)，运用这个式子我们可以构造以下矩阵。

 C(k,),   C(k,),   C(k,),   C(k,)………… …… C(k,k) 　　      (n-)^k            (n)^k

 C(k-,), C(k-,), C(k-,), C(k-,)…………C(k-,k-) 　　    (n-)^(k-)        (n)^(k-)

 C(k-,), C(k-,), C(k-,), C(k-,)…………C(k-,k-) 　　    (n-)^(k-)        (n)^(k-)

 C(k-,), C(k-,), C(k-,), C(k-,)…………C(k-,k-) 　　    (n-)^(k-)    =   (n)^(k-)

 ……………………                                         　  *　　0

 ……………………                                 　　　　　　　　　

 ……………………                                         　　　　

 C(,), C(,), C(,), C(,)                               (n-)^()          (n)^()

 C(,), C(,), C(,)                                       (n-)^()          (n)^()

 C(,), C(,)                                               (n-)^()          (n)^()

 C(k,),   C(k,),   C(k,),   C(k,)………… …… C(k,k)　　　　     s(n-)             s[n]

还有一点这道题有一个奇怪的mod数2^32对于这个膜数我们采用unsigned int自然溢出就好了，如果直接mod就会超时，这一点在以后遇到这个mod数的时候需要注意。

代码：

 //Author: xiaowuga

 #include<bits/c++.h>

 #define maxx INT_MAX

 #define minn INT_MIN

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef unsigned int ll;

 long long n,size;

 struct Matrix{

     ll mat[][];

     void clear(){

         memset(mat,,sizeof(mat));

     }

     Matrix operator * (const Matrix & m) const{

         Matrix tmp;

         int i ,j,k;

         tmp.clear();

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

             for( k=;k<=size+;k++){

                 if(mat[i][k]==) continue;

                 for( j=;j<=size+;j++){

                     tmp.mat[i][j]+=mat[i][k]*m.mat[k][j];

                     //tmp.mat[i][j]%=MOD;

                 }

             }

         return tmp;

     }

 };

 Matrix POW(Matrix m,long long k){

     Matrix ans;

     memset(ans.mat,,sizeof(ans.mat));

     for(int i=;i<=size+;i++) ans.mat[i][i]=;

     while(k){

         if(k&) ans=ans*m;

         k=k>>;

         m=m*m;

     }

     return ans;

 }

 int main() {

      ll tranangle[][]={};

      tranangle[][]=;

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

          tranangle[i][]=;

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

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

      }

      int T;

      scanf("%d",&T);

     for(int Case=;Case<=T;Case++){

        scanf("%lld%lld",&n,&size);

         Matrix m;

         memset(m.mat,,sizeof(m.mat));

         for(int i=;i<=size;i++){

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

                 m.mat[i][j]=tranangle[i][j];

         }

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

              m.mat[size+][i]=tranangle[size][i];

         m.mat[size+][size+]=;

         Matrix ans=POW(m,n-);

         ll sum=;

         for(int i=;i<=size+;i++){

             sum+=ans.mat[size+][i];

         }

         printf("Case %d: %lld\n",Case,sum);

     }

     return ;

 }

巴特西

lightoj1132—Summing up Powers （取膜技巧&&组合数应用）

最新文章

热门文章