ZUFE2480: 神奇的序列 2017-05-12 16:45 39人阅读 评论(0) 收藏

时间：2023-12-15 16:42:02

2480: 神奇的序列

时间限制: 4 Sec  内存限制: 256 MB

提交: 31  解决: 15

[提交][状态][讨论版]

题目描述

序列a如下：

a[0] = A;

a[1] = B;

a[i] = a[pp] * a[qq]; ( i>=2，pp = 向下取整(i/k1)，qq = 向下取整(i/k2) )

有Q次询问，每次询问输入pos，请输出a[pos]%mod。

输入

第一行输入五个整数A，B，k1，k2，mod。

第二行输入一个整数Q。

接下来Q行每行输入一个整数pos。

1<=A<=100

1<=B<=100

2<=k1,k2<=1e14

1<=mod<=1e9+7

1<=Q<=100000

1<=pos<=1e14

输出

输出Q行，每行表示a[pos]%mod。

样例输入

45 87 2 5 1000000007

11

0

1

2

3

4

5

6

7

8

9

10

样例输出

45

87

3915

3915

176175

340605

340605

340605

15327225

15327225

333468568

提示

来源

周甄陶


———————————————————————————————————
思路：记忆化搜索

#include <iostream>

#include <cstdio>

#include <cmath>

#include <map>

#include <set>

using namespace std;

#define LL long long

LL a,b,k1,k2,mod;

map<LL,LL>mp;

set<LL>s;

LL f(LL n)

{

    if(s.count(n)==1)

        return mp[n];

    if(n==0)

    {

        mp[0]=a;

        return a;

    }

    if(n==1)

    {

        mp[1]=b;

        return b;

    }

    LL x=f(n/k1)*f(n/k2)%mod;

    if(s.count(x)==0)

    {

        mp[n]=x;

        s.insert(n);

    }

    return x;

}

int main()

{

    int q;

    LL n;

    while(~scanf("%lld%lld%lld%lld%lld",&a,&b,&k1,&k2,&mod))

    {

            mp.clear(),

            s.clear();

        scanf("%d",&q);

        while(q--)

        {

            scanf("%lld",&n);

            LL ans=f(n);

            printf("%lld\n",ans);

        }

    }

    return 0;

}

相关文章