HDU 5063 Operation the Sequence

举报
Linux猿 发表于 2021/08/04 23:40:13 2021/08/04
【摘要】 做题感悟:这题开始以为是找规律,果断悲剧阿,最后才意识到应该逆着退回去。 解题思路:                 这题的突破口就是要逆向推回去,这样复杂度为 50 * m 的复杂度。做完这题还学到一点就是如果取模的数为素数,可以让指数先对素数减一取模,取模后指数就比较小了。 代码:...


做题感悟:这题开始以为是找规律,果断悲剧阿,最后才意识到应该逆着退回去。

解题思路:

                这题的突破口就是要逆向推回去,这样复杂度为 50 * m 的复杂度。做完这题还学到一点就是如果取模的数为素数,可以让指数先对素数减一取模,取模后指数就比较小了。

代码:


      #include<iostream>
      #include<sstream>
      #include<map>
      #include<cmath>
      #include<fstream>
      #include<queue>
      #include<vector>
      #include<sstream>
      #include<cstring>
      #include<cstdio>
      #include<stack>
      #include<bitset>
      #include<ctime>
      #include<string>
      #include<cctype>
      #include<iomanip>
      #include<algorithm>
      using namespace std  ;
      #define INT __int64
      #define L(x) (x * 2)
      #define R(x) (x * 2 + 1)
      const int INF = 0x3f3f3f3f ;
      const double esp = 0.0000000001 ;
      const double PI = acos(-1.0) ;
      const INT mod = 1e9 + 7 ;
      const int MY = 1e7 + 5 ;
      const int MX = 100000 + 5 ;
      int n ,m ;
      struct node
      {
      int x ,y ;
      }T[MX] ;
      INT pow(INT a ,int k ,INT mod)
      {
       INT b = 1 ;
      while(k)
       {
      if(k&1)
       b = (b*a)%mod ;
       a = (a*a)%mod ;
       k>>= 1 ;
       }
      return b ;
      }
      int main()
      {
      //freopen("input.txt" ,"r" ,stdin) ;
      int Tx ;
      scanf("%d" ,&Tx) ;
      while(Tx--)
       {
      scanf("%d%d" ,&n ,&m) ;
      memset(T ,0 ,sizeof(T)) ;
      char ch ; int x ,temp ;
      for(int i = 0 ;i < m ; ++i)
       {
      cin>>ch>>x ;
      if(ch == 'Q')
       T[i].x = 1 ;
       T[i].y = x ;
       }
      for(int i = 0 ;i < m ; ++i)
      if(T[i].x)
       {
      int num = 0 ,St = T[i].y ;
      for(int j = i ;j >= 0 ; --j)
       {
      if(T[j].x)  continue ;
      if(T[j].y == 1)
       {
      if(n%2)  temp = n/2 + 1 ;
      else temp = n/2 ;
      if(St <= temp)
       St = St*2 - 1 ;
      else St = (St - temp)*2 ;
       }
      else if(T[j].y == 2)
       St = n - St + 1 ;
      else  num++ ;
       }
      if(!num)  cout<<St<<endl ;
      else
      cout<<pow((INT)St ,pow(2 ,num ,mod-1) ,mod)<<endl ;
       }
       }
      return 0 ;
      }
  
 



文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/40082425

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。