首页 > 代码库 > HDU 5063 Operation the Sequence

HDU 5063 Operation the Sequence

2024-07-26 17:30:41   218人阅读

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\n",quick_mod( Q[j].num , Q[j].cnt));        }    }}

 

HDU 5063 Operation the Sequence


联系
我们