首页 > ACM题库 > HDU-杭电 > HDU 2817-A sequence of numbers-分治-[解题报告]HOJ
2014
02-17

HDU 2817-A sequence of numbers-分治-[解题报告]HOJ

A sequence of numbers

问题描述 :

Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help.

输入:

The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence.

You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing.

输出:

The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence.

You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing.

样例输入:

2
1 2 3 5
1 2 4 5

样例输出:

5
16

HDU2817 A sequence of numbers

现在有一个由整数组成的序列,可能是等差数列,也可能是等比数列,但是只给出前3个数,要求你求数列中第k个数% 200907的结果。所给数列是一个非递减数列。

输入:首先是一个t表示输入的实例个数,以下t行每行代表一个实例。每行包括4个整数,前3个整数在[0, 2^63)范围内,表示数列的头3个数,第4个数是k表示要求的数列中的第k个数。其中0 < k <= 10^9。

输出:输出数列中第k个数%200907的结果。

分析:特殊情况,一个非递减数列如果既是等差又是等比数列,那么它一定是有一系列相同的数组成的。或者说如果数列的前2个数相等,那么整个数列都相等。

假设读入的前3个数分别为a1,a2,a3.

如果a2-a1 == a3-a2 那么数列等差,公差为d=a2-a1.所求的第k个数为 ak = a1+d*(k-1)

所求为ak%mod

否则数列为等比数列,公比为p=a2/a1且公比必定为整数(可证),所求的第k个数为ak = a1*(p^(k-1))。所求为ak%mod。该结果要用pow_mod的幂运算分治法求。

求等比的时候 如果 int p=a2/a1;则必定出错,因为p可能超出int范围。

对于这种数据正好几乎要超过int的范围却远小于long long的范围的题目,直接全部用long long

AC代码:

//对于这种数据正好几乎要超过int的范围却远小于long long的范围的题目,直接全部用long long
#include<cstdio>
using namespace std;
const long long mod = 200907;

long long pow_mod(long long x,long long a,long long n)//a^b mod mod
{
    if(a==0) return 1;
    long long ans = pow_mod(x,a/2,n);
    long long temp = (ans*ans)%n;
    if(a%2) temp = (temp*x)%n;
    return temp;
}

/*
long long pow_mod(long long a,long long b,long long n)  //a^b mod n
{
    long long ret=1;
    for (; b; b>>=1,a=(long long)(((long long)a)*a%n))
        if (b&1)
            ret=(long long)(((long long)ret)*a%n);
    //printf("%d\n",ret);
    return ret;
}
*/
int main()
{
    int t;
    scanf("%d",&t);

    while(t--)
    {
        long long  a1,a2,a3;
        long long k;
        scanf("%I64d%I64d%I64d%I64d",&a1,&a2,&a3,&k);
        //if(a1==a2)
        // printf("%.0lf\n",a1%mod);

        if(a2-a1==a3-a2)//等差数列
        {
            /*
            long long d = (long long)(a2-a1);
            long long a = (long long)a1;
            int temp = (a%mod+((d%mod)*((k-1)%mod)))%mod;
            printf("%d\n",temp);
            */
            long long d = (a2-a1)%mod;
            long long temp = ((a1%mod)+((d%mod)*((k-1)%mod)))%mod;
            printf("%I64d\n",temp);

        }
        else//等比数列
        {
            /*
            long long p1 = (a2/a1);
            long long p = (long long)p1;
            long long a = (long long)a1;
            int temp = ((a%mod)*(pow_mod(p,k-1,mod)))%mod;
            printf("%d\n",temp);
            */
            long long p=a2/a1;//p的值可能超过int的范围,如果此处用int则必定WA
            long long  temp = ((a1%mod)*(pow_mod(p,k-1,mod)))%mod;
            printf("%I64d\n",temp);

        }

    }
    return 0;
}

解题参考:http://blog.csdn.net/u013480600/article/details/19180579


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

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

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

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。