hdu4990——多解矩阵快速幂

传送门：http://acm.split.hdu.edu.cn/showproblem.php?pid=4990

Reading comprehension

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2143    Accepted Submission(s): 864

Problem Description

Read the program below carefully then answer the question.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>

const int MAX=100000*2;
const int INF=1e9;

int main()
{
  int n,m,ans,i;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    ans=0;
    for(i=1;i<=n;i++)
    {
      if(i&1)ans=(ans*2+1)%m;
      else ans=ans*2%m;
    }
    printf("%d\n",ans);
  }
  return 0;
}

 

Input

Multi test cases，each line will contain two integers n and m. Process to end of file.
[Technical Specification]
1<=n, m <= 1000000000

 

Output

For each case，output an integer，represents the output of above program.

 

Sample Input

1 10 3 100

 

Sample Output

1 5

 

Source

BestCoder Round #8

 

Recommend

heyang   |   We have carefully selected several similar problems for you:  6216 6215 6214 6213 6212 

题意：题目意思说的很明白了，当然数据量也很说明问题了，就是需要优化实现题面中的函数功能

思路：可能是因为是从专题入手的原因，所以一上来就直接构造矩阵了（这题也很适合练习去构造），开始是把就合并成一种情况去构造，后来林巨有一个比较简单的方法（实现中帮他发现了一个误区），我也觉得根据偶数去推奇数情况比较简单

PS：之前一直用普通写法，今天偶然测试发现封装类重载运算符时间上快很多，所以之后当然要改一下模板了！！！（呵呵，还是自己太菜了）

f[n] = 2*f[n-2] + f[n-1] + 1

代码：

///f[n] = 2*f[n-2] + f[n-1] + 1
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#pragma GCC optimize("02")
#define cl(a,b) memset(a,b,sizeof(a))
#define in freopen("F://1.txt","r",stdin)
#define out freopen("F://2.txt","w",stdout)
using namespace std;
typedef unsigned long long llu;
typedef long long ll;
const ll inf=(ll)1<<60;
const int maxn=100;
ll n, mod;
struct matrix{
    ll a[maxn][maxn];
};
matrix multi(matrix x,matrix y){
    int i,j,k;
    matrix tmp;
    cl(tmp.a, 0);
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            if (!x.a[i][j]) continue;
            for (k=1;k<=n;k++){
                tmp.a[i][k]+=x.a[i][j]*y.a[j][k];
                tmp.a[i][k]%=mod;
            }
        }
    }
    return tmp;
}
matrix power(matrix s,int p){
    int i;
    matrix res;
    cl(res.a, 0);
    for(i=1;i<=n;i++) res.a[i][i]=1;
    while (p){
        if (p&1) res=multi(res,s);
        p>>=1;
        s=multi(s,s);
    }
    return res;
}

int main(){
    n = 3;//和构造矩阵对应
    ll x;
    matrix m;
    cl(m.a, 0);
    m.a[1][1] = 1;m.a[1][2] = 1;
    m.a[2][1] = 2;
    m.a[3][1] = 1;m.a[3][3] = 1;
    matrix m2;
    cl(m2.a, 0);
    m2.a[1][1] = 2;m2.a[1][2] = 1;m2.a[1][3] = 1;
    while(~scanf("%lld %lld", &x, &mod)){
        if(x==1){
            printf("%lld\n", 1%mod);
            continue;
        }
        else if(x==2){
            printf("%lld\n", 2%mod);
            continue;
        }
        else{
        /*cout<<"**************"<<endl;
        for(int i = 1; i <= 3; i++){
            for(int j = 1; j <= 3; j++)
                printf("%d ",ans.a[i][j]);
            printf("\n");
        }
        cout<<"**************"<<endl;*/
            matrix m3;
            m3 = power(m, (x-2));
            matrix ans = multi(m2, m3);
            printf("%lld\n", ans.a[1][1]);
        }
    }
    return 0;
}

偶数时a[n] = a[n-2] * 4 + 2

代码：

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#pragma GCC optimize("02")
#define cl(a,b) memset(a,b,sizeof(a))
#define in freopen("F://1.txt","r",stdin)
#define out freopen("F://2.txt","w",stdout)
using namespace std;
typedef unsigned long long llu;
typedef long long ll;
const ll inf=(ll)1<<60;
const int maxn=100;
ll n, mod;
struct matrix{
    ll a[maxn][maxn];
};
matrix multi(matrix x,matrix y){
    int i,j,k;
    matrix tmp;
    cl(tmp.a, 0);
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++)
        {
            if (!x.a[i][j]) continue;
            for (k=1;k<=n;k++)
            {
                tmp.a[i][k]+=x.a[i][j]*y.a[j][k];
                tmp.a[i][k]%=mod;
            }
        }
    }
    return tmp;
}
matrix power(matrix s,int p){
    int i;
    matrix res;
    cl(res.a, 0);
    for(i=1;i<=n;i++) res.a[i][i]=1;
    while (p){
        if (p&1) res=multi(res,s);
        p>>=1;
        s=multi(s,s);
    }
    return res;
}
int main(){
    ll x, y;
    n = 2;
    matrix t;
    cl(t.a, 0);
    t.a[1][1] = 4;t.a[1][2] = 2;
    t.a[2][1] = 0;t.a[2][2] = 1;
    while(~scanf("%lld %lld",&x,&mod)){
        if(x==1)
            printf("%lld\n",x%mod);
        else{
            y = x/2-1;
            matrix ans = power(t,y);
            ll res = (ans.a[1][1]*2%mod + ans.a[1][2])%mod;
            if(x&1)
                printf("%lld\n",(res*2%mod+1)%mod);
            else
                printf("%lld\n",res);
        }
    }
    return 0;
}

当然还有不用快速幂的直接推公式去优化，表示数学好真的是很强，这里记录一下，以后试着推一下

大牛博客：http://www.cnblogs.com/syhandll/p/4919915.html