首页 > ACM题库 > HDU-杭电 > HDU 1757 A Simple Math Problem-快速幂-[解题报告] C++
2013
12-23

HDU 1757 A Simple Math Problem-快速幂-[解题报告] C++

A Simple Math Problem

问题描述 :

Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.

输入:

The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.

输出:

For each case, output f(k) % m in one line.

样例输入:

10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

样例输出:

45
104

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

盗用一张图:

把问题转化为求矩阵的n-9次幂就行了;

直接上代码了;

#include<iostream>
 #include<cstring>
 const int N=10;
 using namespace std;
 int k,m;
 struct Matrix{
     int map[N][N];
 };
 
 Matrix matrix;
 
 void Initiate(){
     for(int i=0;i<N;i++){
         scanf("%d",&matrix.map[0][i]);
     }
     for(int i=1;i<N;i++){
         for(int j=0;j<N;j++){
             if(i==(j+1))matrix.map[i][j]=1;
             else matrix.map[i][j]=0;
         }
     }
 }
 
 //矩阵相乘
 Matrix Mul(Matrix &a,Matrix &b){
     Matrix c;
     for(int i=0;i<N;i++){
         for(int j=0;j<N;j++){
             c.map[i][j]=0;
             for(int k=0;k<N;k++){
                 c.map[i][j]+=a.map[i][k]*b.map[k][j];
             }
             c.map[i][j]%=m;
         }
     }
     return c;
 }
 
 //快速幂
 Matrix Pow(int n){
     Matrix t;
     if(n==1)return matrix;
     if(n&1)return Mul(matrix,Pow(n-1));
     else {
         Matrix temp=Pow(n>>1);
         return Mul(temp,temp);
     }
 }
 
 
 int main(){
     while(scanf("%d%d",&k,&m)!=EOF){
         Initiate();
         if(k<10){
             printf("%d\n",k%m);
             continue;
         }
         Matrix temp=Pow(k-9);
         int ans=0;
         for(int i=0;i<N;i++){
             ans+=temp.map[0][i]*(N-i-1); //最后要乘上f[9],f[8],...,f[1],f[0];
             ans%=m;
         }
         printf("%d\n",ans);
     }
     return 0;
 }

附上一链接:http://blog.csdn.net/q3498233/article/details/5786180

 

解题报告转自:http://www.cnblogs.com/wally/archive/2013/03/01/2938305.html


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }