HDOJ 5063 Operation the Sequence
注意到查询次数不超过50次,那么能够从查询位置逆回去操作,就能够发现它在最初序列的位置,再逆回去就可以求得当前查询的值,对于一组数据复杂度约为O(50*n)。
1 3 5 O 1 O 2 Q 1 O 3 Q 1
Sample Output2 4
SourceBestCoder Round #13
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long int LL; const LL MOD=1000000007LL; int n,m; char op[10]; int p[110000],np; LL quickpow(LL p,LL x) { LL ret=1; LL e=p; while(x) { if(x%2LL) ret=(ret*e)%MOD; e=(e*e)%MOD; x/=2LL; } return ret%MOD; } LL query(int x) { LL c=1; int pos=x; int half=(n+1)/2; for(int i=np-1;i>=0;i--) { if(p[i]==3) c=(c+c)%(MOD-1); else if(p[i]==2) pos=n-pos+1; else if(p[i]==1) { if(pos<=half) pos=2*(pos-1)+1; else pos=(pos-half)*2; } } return quickpow((LL)pos,c); } int main() { int T_T; scanf("%d",&T_T); while(T_T--) { np=0; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int x; scanf("%s%d",op,&x); if(op[0]=='O') p[np++]=x; else if(op[0]=='Q') printf("%I64d\n",query(x)); } } return 0; }
版权声明:本文博客原创文章。博客,未经同意,不得转载。
优质内容筛选与推荐>>
1、从扩展方法到匿名方法再到LINQ
2、JAVA EE学习目标
3、前端加密办法之混淆js加密
4、3364
5、玩转matlab之一维 gauss 数值积分公式及matlab源代码