快速幂及矩阵快速幂

1.杭电————人见人爱A^B 链接标题
题目简介：求a的b次幂（1<=a,b<=10000）
思路：二分快速幂
注意：为了防止溢出，求和和做乘法都应取余（！！！）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000;
ll quickpow(ll a,ll b)
{
    ll ans=1,base=a;
    while(b)
    {
        if(b&1) ans=(ans*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll a,b;
    while(~scanf("%lld%lld",&a,&b)&&(a||b))
    {
        printf("%lld\n",quickpow(a,b));
     } 
} 

2.杭电————Tr A 链接标题
题目简介：求Tr(A^k)%9973(Tr为矩阵的迹)
思路:矩阵快速幂
注意：用long long 并且在可能溢出的地方取模。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=9973;
ll n;
struct matrix
{
    ll v[20][20];
};
matrix mult(matrix &a,matrix &b)
{
    matrix temp;
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
      {
          temp.v[i][j]=0;
          for(int k=1;k<=n;k++)
        {
            temp.v[i][j]=(temp.v[i][j]+a.v[i][k]*b.v[k][j]%p)%p;
         } 
       } 
    }
    return temp;
}
matrix quickpow(matrix a,ll k)
{
    matrix ans;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
          if(i==j)
        ans.v[i][j]=1;
        else ans.v[i][j]=0;
      }
    while(k)
    {
        if(k&1) ans=mult(ans,a);
        a=mult(a,a);
        k>>=1;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll k;
        scanf("%lld%lld",&n,&k);
        matrix a;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%lld",&a.v[i][j]);
            }
        }
        matrix ans=quickpow(a,k);
        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(i!=j) continue;
                else sum=(sum+ans.v[i][j])%p;
            }
        }
         printf("%lld\n",sum%p);       
    }
}