HDU 5063 Operation the Sequence

Operation the Sequence

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 154    Accepted Submission(s): 74

Problem Description

You have an array consisting of n integers: a1=1,a2=2,a3=3,…,an=n. Then give you m operators, you should process all the operators in order. Each operator is one of four types:
Type1: O 1 call fun1();
Type2: O 2 call fun2();
Type3: O 3 call fun3();
Type4: Q i query current value of a[i], this operator will have at most 50.
Global Variables: a[1…n],b[1…n];
fun1() {
index=1;
  for(i=1; i<=n; i +=2) 
    b[index++]=a[i];
  for(i=2; i<=n; i +=2)
    b[index++]=a[i];
  for(i=1; i<=n; ++i)
    a[i]=b[i];
}
fun2() {
  L = 1;R = n;
  while(L<R) {
    Swap(a[L], a[R]); 
    ++L;--R;
  }
}
fun3() {
  for(i=1; i<=n; ++i) 
    a[i]=a[i]*a[i];
}

 

Input

The first line in the input file is an integer T(1≤T≤20), indicating the number of test cases.
The first line of each test case contains two integer n(0<n≤100000), m(0<m≤100000).
Then m lines follow, each line represent an operator above.

 

Output

For each test case, output the query values, the values may be so large, you just output the values mod 1000000007(1e9+7).

 

 

Sample Input

 

1

3 5

O 1

O 2

Q 1

O 3

Q 1

 

Sample Output

2

4

 

题目有3中操作。

然后问，经过操作后某个位置的数是多少。

可以发现 ，操作3可以最后处理 。

可以通过最后的位置找到原式的位置， 并且原式位置的值a[i]就等于i。

就是一个逆向的过程 ， 然后询问只有50组 ， 就暴力就可以了 。 

处理操作3的时候 ， 快速幂一下 。 

然后因为 mod = 1e9+7 是一个素数 ， 

所以计算 ( A^k ) % (mod ) 的时候 k要模一下 ( mod -1 )  , 不然会超时， 这里卡了一下 。

如果 mod 不是素数的话就求一下 欧拉函数 就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int N = 100010;

struct node
{
    LL num ,cnt;
    int id ;
    bool is_Q;
} e[N] ,Q[N] ;

LL quick_mod( LL a , LL b )
{
    LL res = 1 ;
    while( b )
    {
        if( b&1 ) res = res * a % mod ;
        a = a * a % mod ;
        b >>= 1;
    }
    return res ;
}


int main()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif // LOCAL

    int _ ,n , m ;
    char s[5];
    LL x ;
    scanf("%d",&_);
    while( _-- ){
        scanf( "%d%d",&n,&m );
        for( int i = 0 ; i < m ; ++i ){
            scanf("%s%I64d",s,&x);
            if( s[0] == 'Q' )  e[i].is_Q = 1;
            else e[i].is_Q = 0 ;
            e[i].num = x , e[i].id = i , e[i].cnt = 1 ;
        }

        while( m > 0 && !e[m-1].is_Q ) m--;

        int tail = 0 ;

        for( int i = m -1  ; i >= 0 ; --i ){

            if( e[i].is_Q ){ Q[tail++] = e[i] ; continue ; }

            for( int j = 0; j < tail ; ++j ){
                if( e[i].num == 1 ){
                    int mid = ( n + 1 ) / 2 ;
                    if( Q[j].num <= mid ) Q[j].num = 2 * Q[j].num - 1 ;
                    else Q[j].num = 2 * ( Q[j].num - mid );
                }
                else if( e[i].num == 2 ){
                    Q[j].num = n - Q[j].num + 1 ;
                }
                else {
                    Q[j].cnt = Q[j].cnt * 2 % (mod - 1) ;
                }
            }

        }
        for( int j = tail - 1 ; j >=0 ; --j ){
            printf("%I64d
",quick_mod( Q[j].num , Q[j].cnt));
        }
    }
}