序列"/>
ZUFE2480: 神奇的序列
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 longLL 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;
}
更多推荐
ZUFE2480: 神奇的序列
发布评论