MYF

HDU 5063 Operation the Sequence

题目链接

HDU 5063

解题方法:推导 + 反向模拟

题目分析

题目大意

先给出一个数字n,形成一个长度为n的数组,ai = i,现在有四种操作。第一种,取所有奇数位置的值,再取所有偶数位置的值。第二种,n个位置的元素关于中心对称,形成新的数列。第三种,将每一个位置的值平方。第四种,查询之前的操作全部完成之后某一位置的值。

解析

看题目很容易发现,最多执行五十次操作,所以每次查询的时候计算的话复杂度并不会很大。分析一下这个问题,看前三种操作,后两种还是挺容易的,对称的话直接找n+1-pos即可找到原来的位置,值平方的话只需要一直平方即可,因为二进制位只有一个1,所以快速幂在这种情况下完全没有优势,直接乘即可,最多也就50次。麻烦一点的是第一个问题,要分n为奇数和n为偶数两种情况考虑。当n为奇数时,对于这n个位置的奇数位,new = ( old + 1 ) / 2,对于偶数位 new = old / 2 + ( n - n / 2 )。再看n为偶数的情况,上面两个公式仍然成立,所以只需要倒推一下,找出来old关于new的位置变换公式即可。查询的时候直接跑那么多次的平方即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n) (i == n ? '\n' : ' ')
#define hi printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define mp make_pair
#define pb push_back
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
/*
fun1() // 取所有奇数位置 再取所有偶数位置
fun2() { // 中心对称
fun3() { // 每个数乘方
*/
int op[maxn],stp=0,t,n,m;
int main(){
int pos;
char s[2];
scanf("%d",&t);
int mi=0;
while (t--) {
stp=0;
mi=0;
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++) {
scanf("%s%d",s,&pos);
if (s[0]=='O'&&pos==1)
op[stp++]=1;
else if (s[0]=='O'&&pos==2)
op[stp++]=0;
else if (s[0]=='O'&&pos==3)
mi++;
else{
ll tmp = pos;
for (int i=stp-1; i>=0; i--)
if (op[i]==1&&tmp<=(n+1)/2)
tmp=2*tmp-1;
else if(op[i]==1)
tmp=tmp*2-2*(n-n/2);
else if(op[i]==0)
tmp=n+1-tmp;
for (int i=1; i<=mi; i++)
tmp=tmp*tmp%mod;
printf("%lld\n",tmp);
}
}
}
return 0;
}