首页 > ACM题库 > HDU-杭电 > HDU 3411-Snail Alice-快速幂-[解题报告]HOJ
2014
03-23

HDU 3411-Snail Alice-快速幂-[解题报告]HOJ

Snail Alice

问题描述 :

Snail Alice is a snail indulged in math. One day, when she was walking on the grass, suddenly an accident happened. Snail Alice fell into a bottomless hole, which was deep enough that she kept falling for a very long time. In the end, she caught the lateral wall of the hole and stop falling down. She named the place where she stopped “lucky place” immediately.

Snail Alice decided to climb up along the wall from the “lucky place”. The first day she climbed up q0 (q is a positive constant integer) metres, but at night when she fell asleep, she fell down q1 metres. She was shocked when she woke up, and she decided to make an extra effort. The second day she finally climbed up q2 metres. To her surprise, she fell down faster because of the tiredness. She fell down q3 metres at night. The longer she climbed up the longer she fell down. But finally, she still climbed out of the hole and slept on the ground.

Lying on the grass safe, she was curious about a question. How many metres was the “lucky place” down under the ground? She remembered that the sum of the times of her climbing up and falling down is n(of course, n is odd), so the distance between the ground and the “lucky place” must be 1-q+q2-q3+…+(-1)n-1qn-1. Snail Alice simplified that long formula and get a beautiful result: (qn+1)/(q+1). But as a math professor, she wouldn’t stop. She came up with a good problem to test her students. Here is the problem:

A function f(n), n is a positive integer, and

Passing the Message

Given q and n, please calculate the value of f(n).Please note that q and n could be huge.

输入:

Input consists of multiple test cases, and ends with a line of “-1 -1 -1”.
For each test case:
The first line contains three integers x1, y1 and z1, representing q. q=x1^y1+z1.
The second line contains two integers: y2 and z2, representing n. n=2^y2+z2.
The third line contains a single integer P, meaning that what you really should output is the formula’s value mod P.
Note: 0<=x1,y1,z1,y2,z2<=50000, z1>0, 0<P<100000000

输出:

Input consists of multiple test cases, and ends with a line of “-1 -1 -1”.
For each test case:
The first line contains three integers x1, y1 and z1, representing q. q=x1^y1+z1.
The second line contains two integers: y2 and z2, representing n. n=2^y2+z2.
The third line contains a single integer P, meaning that what you really should output is the formula’s value mod P.
Note: 0<=x1,y1,z1,y2,z2<=50000, z1>0, 0<P<100000000

样例输入:

2 1 3
0 0
32551
3 0 5
0 2	
70546
-1 -1 -1

样例输出:

1
31

其实这题也算是看解题报告练得一题,不过还是很有收获的。

碰到这种求大数函数值时,果断最先想到矩阵快速幂。。。把f(x)写成递推公式的形式。问题是这个函数还来个大括号,还要讨论,咋搞?

首先是对公式的处理(⊙﹏⊙b汗,就是这步想不到,所以果断看来解题报告),直接多项式除法(orz…..算是真心长姿势了),得出f(n)=x^(n-1)-x^(n-2)+….+1(n为奇数),f(n)=x^(n-1)-x^(n-2)+…x-1(n为偶数),这就看出规律了,f(n)=q*f(x-1)+1(n为奇数),f(n)=q*f(x-1)-1(n为偶数)。先看当n为奇数时的情况,这个+1是个碍事的东西,怎么办?其实稍加改变就OK了(我看的某份结题报告竟然是硬推!!!这个其实并不好)把f(n)改写成f(n)=(q-1)f(x-1)+f(x-1)-1=(q-1)f(x-1)+x^(n-1)-x^(n-2)+…+x-1+1=(q-1)f(x-1)+qf(x-2)。。。当n为偶数时,也是类似的,也能推出此公式,过程略掉。。。。哈哈,搞定。。然后矩阵快速幂就OK了。。这题时间卡的太狠,本人代码挫出翔,竟然是过这题当中时间最慢的(。。。。。),用C++才能过,G++跪。。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

#define N 50005
#define M 30
#define read(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define cl(a) memset(a,0,sizeof(a))
#define ll long long

ll x[M],f[3],r[N][3][3],q;
int p;
 
using namespace std;

ll bin(ll t)
{
    ll res=1;
    int i=0;
    while (t>0)
    {
        if (t&1) res=(res*x[i])%p;
        i++;
        t>>=1;
    }
    return res;
}

void init()
{
    r[0][1][1]=(q-1+p)%p;
    r[0][1][2]=q;
    r[0][2][1]=1;
    r[0][2][2]=0;
    f[1]=1;f[2]=0;
}

void mul(int t)
{
    int i,j,k;
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
        {
            r[t][i][j]=0;
            for (k=1;k<=2;k++) r[t][i][j]=r[t][i][j]+(r[t-1][i][k]*r[t-1][k][j])%p; 
        }
}

void zmul(int i)
{
    ll g1,g2;
    g1=(f[1]*r[i][1][1])%p+(f[2]*r[i][1][2])%p;
    g2=(f[1]*r[i][2][1])%p+(f[2]*r[i][2][2])%p;
    f[1]=g1%p;f[2]=g2%p;
}

void bin2(int t)
{
    int i=0;
    while (t>0)
    {
        if (t&1) zmul(i);
        t>>=1;
        i++;
    }   
}

int main()
{
    int x1,y1,z1,y2,z2,i,j;
    while (read(x1,y1,z1)!=EOF)
    {
        if (x1==-1&&y1==-1&&z1==-1) break;
        read(y2,z2,p);
        cl(x);
        x[0]=x1%p;
        for (i=1;i<M;i++) x[i]=(x[i-1]*x[i-1])%p;
        q=(bin(y1)+z1)%p;
        init();
        for (i=1;i<N;i++) mul(i);
        zmul(y2);
        if (z2>0) bin2(z2-1);
        if (z2>=1) printf("%d\n",f[1]);
        else printf("%d\n",f[2]);
    }
    return 0;
}

 

参考:http://blog.csdn.net/liverpippta/article/details/8255493


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }