首页 > ACM题库 > HDU-杭电 > hdu 2604 Queuing-快速幂-[解题报告]C++
2014
02-10

hdu 2604 Queuing-快速幂-[解题报告]C++

Queuing

问题描述 :

Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time.

  Now we define that ‘f’ is short for female and ‘m’ is short for male. If the queue’s length is L, then there are 2L numbers of queues. For example, if L = 2, then they are ff, mm, fm, mf . If there exists a subqueue as fmf or fff, we call it O-queue else it is a E-queue.
Your task is to calculate the number of E-queues mod M with length L by writing a program.

输入:

Input a length L (0 <= L <= 10 6) and M.

输出:

Input a length L (0 <= L <= 10 6) and M.

样例输入:

3 8
4 7
4 8

样例输出:

6
2
1

点击打开hdu 2604

思路: 递推+矩阵快速幂

分析;

1 根据题目的意思,我们可以求出F[0] = 0 , F[1] = 2 , F[2] = 4 , F[3] = 6 , F[4] = 9 , F[5] = 15

2 那么根据上面前5项我们可以求出n >= 5的时候 F[n] = F[n-1]+F[n-3]+F[n-4]

    那么我们就可以构造出矩阵

    | 1 0 1 1 |     | F[n-1] |    | F[n] |

    | 1 0 0 0 |  *  | F[n-2] | = | F[n-1] |

    | 0 1 0 0 |     | F[n-3] |    | F[n-2] |

    | 0 0 1 0 |     | F[n-4] |    | F[n-3] |

代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-08-23                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int N = 4;

int n , MOD;
struct Matrix{
    int64 mat[N][N];
    Matrix operator*(const Matrix& m)const{
        Matrix tmp;
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                tmp.mat[i][j] = 0;
                for(int k = 0 ; k < N ; k++){
                    tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
                    tmp.mat[i][j] %= MOD;
                }
            }
        }
        return tmp;
    }
};

int Pow(Matrix &m){
    if(n <= 3) 
        return (2*n)%MOD;
    if(n == 4)
        return 9%MOD;
    n -= 4;
    Matrix ans;
    memset(ans.mat , 0 , sizeof(ans.mat));
    for(int i = 0 ; i < N ; i++)
        ans.mat[i][i] = 1;
    while(n){
        if(n&1)
            ans = ans*m;
        n >>= 1;
        m = m*m;
    }

    int sum = 0;
    sum += ans.mat[0][0]*9%MOD;
    sum += ans.mat[0][1]*6%MOD;
    sum += ans.mat[0][2]*4%MOD;
    sum += ans.mat[0][3]*2%MOD;
    return sum%MOD;
}

int main(){
    Matrix m;
    while(scanf("%d%d" , &n , &MOD) != EOF){
        memset(m.mat , 0 , sizeof(m.mat));
        m.mat[0][0] = m.mat[0][2] = m.mat[0][3] = 1;
        m.mat[1][0] = m.mat[2][1] = m.mat[3][2] = 1;
        printf("%d\n" , Pow(m));
    }
    return 0;
}

解题转自:http://blog.csdn.net/chenguolinblog/article/details/10229221


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }