hdu 2842 Chinese Rings

点击打开hdu2842

思路: 矩阵快速幂

分析:

1 题目的意思是给定n个环,和一些规则要把所有的环全部拆下最少需要的步数

2 题目规定如果要拆第n个环,那么第n-1个要挂着,n-2环要被拆下。那么我们设f(n)表示拆下前n个环的最少的步骤

   那么考虑第n个环的情况,第n-1个环必须要挂着,n-2环要拆下,那么这一步就要f(n-2),拆下第n个需要1步。然后只剩下第n-1个环,由于n-1环需要第n-2环挂着,所以我们需要把前n-2个环挂上去,所以需要f(n-2),剩下n-1个需要拆下需要f(n-1)。那么总的需要f(n) = f(n-2)+1+f(n-2)+f(n-1) => f(n) = 2*f(n)+f(n-1)+1

3 接下来利用矩阵快速幂即可

代码:

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

typedef long long int64;
const int MOD = 200907;
const int N = 3;

int n;
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){
    Matrix ans;
    if(n <= 1)
       return n;
    memset(ans.mat , 0 , sizeof(ans.mat));
    for(int i = 0 ; i < N ; i++)
        ans.mat[i][i] = 1;
    n--;
    while(n){
        if(n&1)
            ans = ans*m;
        n >>= 1;
        m = m*m;
    }
    int sum = 0;
    sum += ans.mat[0][0]%MOD;
    sum %= MOD;
    sum += ans.mat[0][2]%MOD;
    return sum%MOD;
}

int main(){
    Matrix m;
    memset(m.mat , 0 , sizeof(m.mat));
    m.mat[0][0] = 1 , m.mat[0][1] = 2 , m.mat[0][2] = 1;
    m.mat[1][0] = 1 , m.mat[2][2] = 1;
    while(scanf("%d" , &n) && n)
         printf("%d\n" , Pow(m));
    return 0;
}
时间: 2024-11-18 14:03:54

hdu 2842 Chinese Rings的相关文章

hdu 1691 Chinese Chess

     一道很简单的模拟题,但是数据比较坑,应该是随机数据     要注意:       棋子不在自己的可能位置,将,士,相 详见代码: #include <iostream> #include <cstdio> using namespace std; int map[11][10]; int x[2],y[2]; int abs(int a){return a>0?a:-a;} bool s(int x,int y,int xi,int xm,int yi,int ym

矩阵快速幂专题【完结】

第一题 hdu 1757 A Simple Math Problem 点击打开链接 思路:矩阵快速幂 分析: 1 最简单的矩阵快速幂的题目,直接利用矩阵求解即可 点击打开查看代码 第二题 hdu 1575 Tr A 点击打开hdu 1575 思路: 矩阵快速幂 分析: 1 题目给定一个n*n的矩阵要求矩阵的k次幂之后的矩阵的对角线的和 2 矩阵快速幂的裸题 点击打开查看代码 第三题 hdu 2604 Queuing 点击打开hdu 2604 思路: 递推+矩阵快速幂 分析; 1 根据题目的意思,

HDU 1546 Idiomatic Phrases Game

链接: http://acm.hdu.edu.cn/showproblem.php?pid=1546 题目: Idiomatic Phrases Game Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 969    Accepted Submission(s): 300 Problem Description Tom is playi

HDU 4081 Qin Shi Huang&#039;s National Road System (次小生成树算法)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=4081 题目: Problem Description During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China ---- they were Qi, Chu, Yan, Han, Zhao, Wei and Qin. Ying Zheng was the

hdu 1527

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1527 hint:威佐夫博弈 基本类似于模板 #include <iostream> #include <cmath> #include <cstdio> using namespace std; const double q = (1 + sqrt(5.0)) / 2.0; // 黄金分割数 int Wythoff(int a, int b) { if (a > b)

hdu 2551 竹青遍野

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2551 hint:就是读懂题就行了 #include <iostream> #include <cstdio> using namespace std; typedef long long LL; LL data[1005]; int main() { data[0]=0; for(int i=1; i<1005; i++) data[i]+=data[i-1]+i*i*i; LL

hdu 2054 A == B?

http://acm.hdu.edu.cn/showproblem.php?pid=2054 此题巨坑,刚开始我以为是简单的水题,就用strcmp过, but错了,后来经过我苦思冥想,结果还有几组数据 0.0 和 0,1.000和1.0 , 但是我不太确定前面的0是不是有作用我还是写了,但是有人过的时候,前面的0没考虑比如: 002和2可能是相等的,也可能是不想等的所以不用判断,只能说明hdu数据不是很强啊,嘿嘿 代码如下: #include <iostream> #include <c

hdu 4430 Yukari&#039;s Birthday

点击打开链接hdu 4430 思路:枚举r+二分k 分析: 1 题目要求的是找到一组最小的r*k,如果r*k相同那么就找r最小的. 2 很明显k>=2,根据n <= 10^12,那么可以知道r的最大值r<50,所以只要枚举枚举r的值,然后二分k的大小找到所有的解,存入一个结构体里面,然后在对结构体排序,那么这样就可以得到最后的ans 3 注意题目说了中心点最多一个蜡烛,所以写二分的时候应该注意判断的条件: 4 还有可能计算得到结果超了long long直接变成负数所以应该对或则个进行判断

hdu 1238 Substrings

点击打开链接hdu 1238 思路:kmp+暴力枚举子串 分析: 1 题目要求找到一个子串x,满足x或x的逆串是输入的n个字符串的子串,求最大的x,输出x的长度 2 题目的n最大100,每一个字符串的最大长度为100,那么暴力枚举子串就是o(n^2)才10000肯定是不会超时的,但是由于这里涉及到了逆串的问题,所以我们应该还要求出n个子串的逆串,然后在求最大的x. 代码: #include<iostream> #include<algorithm> #include<cstd