（转载）HDU4565

（转载）HDU4565

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4565

这个博客讲的比较好：http://blog.csdn.net/ljd4305/article/details/8987823

题意：给定a,b,,n,m,求Sn

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include<cmath>

 #include<sstream>

 #include<string>

 using namespace std;

  __int64 b,k,n,mod;

 struct matrix

 {

     __int64 m[][];

 };

 matrix a,per,s,ans;

 void init()//初始化 *** 作

 {

     s.m[][]=((*((k%mod)*(k%mod))%mod)%mod+(*b)%mod)%mod;

     s.m[][]=(*(k%mod))%mod;

     s.m[][]=;

     s.m[][]=;

     a.m[][]=(*(k%mod))%mod;

     a.m[][]=;

     a.m[][]=(((b%mod)-((k%mod)*(k%mod))%mod)+mod)%mod;

     a.m[][]=;

 }

 matrix mul(matrix x,matrix y)

 {

     matrix temp;

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

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

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

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

         temp.m[i][j]=(temp.m[i][j]+x.m[i][k]*y.m[k][j])%mod;

     return temp;

 }

 matrix mpow(matrix A,__int64 n)

 {

     matrix B;

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

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

         B.m[i][i]=;

     while(n>)

     {

         if(n&)

             B=mul(B,A);

         A=mul(A,A);

         n>>=;

     }

     return B;

 }

 int main()

 {

   while(~scanf("%I64d%I64d%I64d%I64d",&k,&b,&n,&mod))

     {

         init();

         if(n==)

         {

             cout<<(*(k%mod))%mod<<endl;

             continue;

         }

         else if(n==)

         {

             cout<<((*(k%mod)*(k%mod))%mod+(*(b%mod))%mod)%mod<<endl;

             continue;

         }

         else

         {

             ans=mpow(a,n-);

             ans=mul(s,ans);

             cout<<ans.m[][]<<endl;

         }

     }

     return ;

 }