首页 > ACM题库 > HDU-杭电 > hdu 2635 Linux Kernel Version-快速幂-[解题报告]C++
2014
02-12

hdu 2635 Linux Kernel Version-快速幂-[解题报告]C++

Linux Kernel Version

问题描述 :

Samuel is fed up with Microsoft Windows system. Instead of xp he chose to install Linux Fedora 10 in his own desktop. But Linux has various distributions with different kernel versions. Some kernels are not stable. Of course,the unstable ones is not of Samuel’s choice. Samuel is never tired of reinstalling Linux,because he always wants to try the latest release version on his computer. So Samuel needs to know the kernel’s version before he downloads the distribution version.
Here is an easy problem for you,tell Samuel which distribution he should choose to reinstall.
To make the problem easier,suppose each Linux kernel version mark is made up by a string like the format:”r.x.y”Here r represents the major version number,x will be even(stable) or odd(beta version not stable,need to be developed),y represents the time the kernel has been corrected. For instance,the kernel whose number is 2.6.7 is a stable version. However,2.5.11 is not due to the number the letter x represents is odd.
As for he problem which one is the latest kernel,you can also refer to version number. When compared two version,you should first compare the r1 and r2, if r1>r2 version 1 is the latest version. If r1=r2,you need to compare x1 and x2,if x1>x2 that means the version 1 is the latest. If x1=x2,then you need to compare y1 and y2,version 1 is the newest one only if y1>y2..Not clear about my English explanation,you can see the HDOJ 1976,it has a Chinese one.

输入:

The input will consist 2 major parts:
Test cases t.
Each of test case is made up of 2 minor parts:
1.The number of available distributions
2.Name of the distribution(a string,no white blanks)
3.The kernel version(also a string in the format r.x.y without any blanks)
I guarantee there is no test case has the same distribution name but with different kernel version nor the same kernel version but with the different distribution name. All the information in the same test cases is totally different.

输出:

The input will consist 2 major parts:
Test cases t.
Each of test case is made up of 2 minor parts:
1.The number of available distributions
2.Name of the distribution(a string,no white blanks)
3.The kernel version(also a string in the format r.x.y without any blanks)
I guarantee there is no test case has the same distribution name but with different kernel version nor the same kernel version but with the different distribution name. All the information in the same test cases is totally different.

样例输入:

2
3
SUSE 2.6.5
Fedora 2.6.7
Ubuntu 2.6.6
4
RedFlag 2.4.5
CentOS 2.5.6
Fedora 2.4.3
Debian 2.5.7
(In reality,the kernel version may not be so. The numbers are made up by myself.)

样例输出:

The latest distribution Samuel will choose is Fedora.
The latest distribution Samuel will choose is RedFlag.

#include <stdio.h>
#include <cstring>
#define mod 9999997
long long tmp[3][3],ans[3][3],a[3][3];
void mul(long long a[][3],long long b[][3])
{
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
        {
            tmp[i][j]=0;
            for(int k=1; k<=2; k++)
                tmp[i][j]+=a[i][k]*b[k][j];
            if(tmp[i][j]>=mod) tmp[i][j]%=mod;
        }
    memcpy(a,tmp,sizeof(tmp));
}
void pow(long long ans[][3],long long b[][3],int n)
{
    ans[1][1]=ans[2][2]=1;
    ans[1][2]=ans[2][1]=0;
    while(n)
    {
        if(n&1) mul(ans,b);
        mul(b,b);
        n>>=1;
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        memset(ans,0,sizeof(ans));
        a[1][1]=3;
        a[1][2]=a[2][2]=1;
        a[2][1]=0;
        pow(ans,a,n);
        printf("%d\n",ans[1][2]%mod);
    }
    return 0;
}

解题转自:http://blog.csdn.net/ehi11/article/details/8616643


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。