zufe 问题 S: 神奇的序列

序列"/>

zufe 问题 S: 神奇的序列

题目描述

序列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

输出

这道题主要是数据太大了，但是仔细观察就会发现，虽然有1e14，但是其实用不到这么这么多的空间去打表（打表也会超时），这时候用map加记忆化搜索就能出解

#include <bits/stdc++.h>
using namespace std;int A, B;
long long k1, k2;
int mod;
int Q;map<long long, int>mp;long long F(long long i)
{if (mp.count(i) == 1)return mp[i];if (i == 0)return mp[i] = A;else if (i == 1)return mp[i] = B;return mp[i] = (F(i / k1) * F(i / k2)) % mod;
}int main()
{while (~scanf("%d%d%lld%lld%d", &A, &B, &k1, &k2, &mod)){mp.clear();int Q;scanf("%d", &Q);while (Q--){long long pos;scanf("%lld", &pos);F(pos);printf("%d\n", mp[pos]);}}return 0;
}