巨难!!!

去年六省联考唯一的一道黑牌题，我今天一天从早到晚，把它从暴力15分怼到了90分，极端接近正解了。

bzoj上A了，但是洛谷和loj上面就不行。伪正解会T，奇奇怪怪的类正解会WA。。

那么，网上的题解多得很，我就不细说了。

着重说一下我的理解感受和坑点。

1.不愧是黑牌题，显得十分的繁杂(并不)。

首先要用到扩展欧拉定理，φ()，还有线段树辅助，快速幂，大量奇奇怪怪的小细节.....要人命啊。

2.根据之前那题，我们可以得知当一个数被操作很多很多很多很多次之后就不变了，成为一个常数。

3.我们首先算出这个次数：phi()到1就是了。特别的，phi(2)=1之后还要再写个phi(1)=1，否则会错。证明网上也很多，我比较推崇这个。(该证明并没有被再次找到......)

4.第一个坑点来了：(c^c^i)%p ≠ (c^((c^i)%p))%p 什么意思呢？意思就是你改一次之后不能接着改第二次，会WA。打暴力时就是这一点卡停了我的思路。如何解决：真·暴力！从初始值a[i]开始重新改起。我：......

5.解决了上面那一件事之后，我们开始着手研究扩展欧拉公式降次的那个式子。把(c^c^i)%p化开之后再一步步推下去，最后我们可以得到这么一个可爱的函数：

 

1 LL cal(int k,int t) 2 { 3     while(t>0) 4     { 5         if(k>=p[t]) k=qpow(c,k%p[t]+p[t],p[t-1]); 6         else k=qpow(c,k,p[t-1]); 7         t--; 8     } 9     return k;10 }

看，它是如此的Cuty and goffy(?)，这里有个p[]数组，是之前预处理出来的每一层phi(P)。

6.然后加上一个线段树，它滋磁区间求和，区间修改(每次修改到底)，并记录一个times表示修改的次数。

7.当某次修改时，如果times已经=cnt了，就return。否则修改，update。

8.开开心心的一交，又WA又T......

9.仔细观察发现：那个可爱的cal中的判断条件if(k>=p[t])显然有误。原因是计算卡速米(kasumi)时已经把结果%p[t-1]了，而上一层的p[t-1]就是这一层的p[t]，于是那个if不会触发。

10.翻看胡雨菲的题解，发现他把kasumi改了下，在kasumi里记录flag，保证了正确性。

11.交上去：T了两个点。90分，bzojAC。本着不放弃不抛弃的原则继续调试，发现要优化掉kasumi的时间复杂度，预处理一下。

12.那么怎么确定flag呢？①也预处理好。②每次在cal里记录一个tag，然后用log c p[t]<=tag来判定。

13.首先写①，写炸了。然后写②，解决了T但是又WA了，依旧90分。然后转①，继续炸。但是理论上两种方法都能AC。

14.over。

WA的代码就不放了。放个11.中的代码。

 

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 typedef long long LL;  6 const int N = 50010;  7 LL a[N],sum[N<<2],times[N<<2],p[N],c,P,cnt;  8 inline LL read()  9 { 10     LL ans=0,f=1;char ch=getchar(); 11     while(ch<'0'||ch>'9') {
    if(ch=='-')f=-1;ch=getchar();} 12     while(ch>='0'&&ch<='9') {ans=ans*10;ans+=(ch-'0');ch=getchar();} 13     return ans*f; 14 } 15 inline LL qpow(LL a,LL b,LL m,bool &flag) 16 { 17     LL ans=1; 18     flag=0; 19     while(b) 20     { 21         if(b&1) 22         { 23             ans=ans*a; 24             if(ans>=m) flag=1,ans%=m; 25         } 26         b=b>>1; 27         a=a*a; 28         if(a>=m) flag=1,a%=m; 29     } 30     return ans; 31 } 32 inline LL phi(LL x) 33 { 34     LL ans=x; 35     for(register int i=2;i*i<=x;i++) 36     { 37         if(x%i==0) 38         { 39             while(x%i==0) x/=i; 40             ans=(ans/i)*(i-1); 41         } 42     } 43     if(x>1) ans=(ans/x)*(x-1); 44     return ans; 45 } 46 inline void pre() 47 { 48     p[0]=P; 49     while(P>1) 50     { 51         p[++cnt]=phi(P); 52         P=p[cnt]; 53     } 54     p[++cnt]=1; 55     P=p[0]; 56     return; 57 } 58 inline void update(LL l,LL r,LL o) 59 { 60     sum[o]=sum[o<<1]+sum[o<<1|1]; 61     times[o]=min(times[o<<1],times[o<<1|1]); 62     return; 63 } 64 inline void build(LL l,LL r,LL o) 65 { 66     if(l==r) 67     { 68         sum[o]=a[r]%P; 69         return; 70     } 71     int mid=(l+r)>>1; 72     build(l,mid,o<<1); 73     build(mid+1,r,o<<1|1); 74     update(l,r,o); 75     return; 76 } 77 inline LL cal(int k,int t) 78 { 79     bool flag=(k>=p[t]); 80     while(t>0) 81     { 82         if(flag) k=qpow(c,k%p[t]+p[t],p[t-1],flag); 83         else k=qpow(c,k,p[t-1],flag); 84         t--; 85     } 86     return k; 87 } 88 inline void add(int L,int R,int l,int r,int o) 89 { 90     if(times[o]>=cnt) return; 91     if(l==r) 92     { 93         times[o]++; 94         sum[o]=cal(a[r],times[o]); 95         return; 96     } 97     int mid=(l+r)>>1; 98     if(L<=mid) add(L,R,l,mid,o<<1); 99     if(mid
         
          >1;108     return (ask(L,R,l,mid,o<<1)+ask(L,R,mid+1,r,o<<1|1))%P;109 }110 int main()111 {112     LL m,n;113     //scanf("%lld%lld%lld%lld",&n,&m,&P,&c);114     n=read();m=read();P=read();c=read();115     for(register int i=1;i<=n;i++) a[i]=read();//scanf("%lld",&a[i]);116     pre();117     build(1,n,1);118     LL flag,x,y;119     for(register int i=1;i<=m;i++)120     {121         //scanf("%d%d%d",&flag,&x,&y);122         flag=read();123         x=read();y=read();124         if(flag) printf("%lld\n",ask(x,y,1,n,1));125         else add(x,y,1,n,1);126     }127     return 0;128 }
         
        
       
      

 

题外话：可以看见我加了很多的常数优化，但是洛谷的#9和#11两个点剧毒。关于WA就放个吧，可以看出#3和#11比较毒，每次WA都有你们。

 

15分暴力->90分花了我一个上午。之后下午晚上都在优化那最后10分，还没搞出来。效率堪忧啊。其实可以搞一搞其他几道题的。

明天就是省选了。敬请收看：省选酱油记。