喜闻乐见的交互题。
开场一看$T1$，这不显然暴力都能过吗？然后就直接开始写暴力。
磨磨叽叽半天写完暴力，过了俩大样例，结果有个细节没处理直接爆零。
然后一看$T2$是个大神线段树，读错题了，反正不好写就先进了$T3$
结果发现$T3$比较对胃口，一个多小时把它砸出来了。
最后回去想打$T2$暴力，写了个线段树死活不过样例，这时候才发现自己读错题，然后就爆零了（根本没想交
不得不吐槽神仙$spj$，动了$T3$的人一大半都是负分。。。强大的（乱）判作弊系统。
而且只要有部分分就算满分是什么操作啊。。。白写那么半天。。。
T1：Eclipse
大意：$A_i=(xA_{i-1}+yA_{i-2}+z)mod \ p,S_i=S_{i-1} + [A_i=C]$。多次询问求$S_r-S_{l-1}$。$p,q \le 10007$
暴力找循环节$p^2$硬干，跑不满，比正解快，但是要用前缀和，而不能处理出所有点然后$lower \ bound$。内存使用不连续。
这种方法的内存消耗很大，但是根据题目性质开$short$就可以。如果你写个离线那么空间就更小了。
正解的话说起来简单：BSGS找矩阵循环节来统计C值出现次数。
然而代码写起来会暴毙，写一半丢掉了。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int c; short sum[100140052];
4 long long re(){
5 register long long p=0;register char ch=getchar();
6 while(!isdigit(ch))ch=getchar();
7 while(isdigit(ch))p=p*10+ch-48,ch=getchar();
8 return p;
9 }
10 long long cal(long long x){return x<c?sum[x]:(x-1)/c*(sum[c+1]-sum[1])+sum[(x-1)%c+1];}
11 int main(){
12 register int t,_=0,q;long long X,Y;
13 cin>>t;while(t--){
14 const int A=re(),B=re(),x=re(),y=re(),z=re(),p=re(),v=re();cin>>q;
15 sum[1]=A==v; sum[2]=(B==v)+sum[1];const int C=(A*y+B*x+z)%p; sum[3]=(C==v)+sum[2];
16 int ls=C,th=(C*x+B*y+z)%p,r;
17 for(c=4;ls!=B||th!=C;++c)sum[c]=sum[c-1]+(th==v),r=ls,ls=th,th=(r*y+th*x+z)%p; c-=3;
18 while(q--)X=re(),Y=re(),printf("%lld\n",cal(Y)-cal(X-1));
19 }
20 }
View Code
T2：Emerald
大意：序列上每个点分$A,B$两类且有权值，相邻两点之间有单向边，若一个$A$点直接或间接可达一个权值更大的$B$点，则这个$A$点会有$1$贡献。
支持查询全局总贡献，单点修改权值，区间翻转边的方向。$n,q \le 10^5,V_i \le 75$
线段树，维护区间内：已有贡献，区间内权值为$k$的能走到左/右端点的未找到$B$的$A$的个数，区间内的边的方向是否一致且是哪个方向，
区间是否存在一个$A$点能同时到达两端（显然只有一个，记录他的权值）。懒标记。以及当整个区间被翻转后的上述信息。
然后这题就没了，细节了。$O(75qlogn)$
T3：Entropy
大意：交互，实现一个结构题，不许使用结构体外的空间（禁止数据传输）。要求建立一种二进制串与$[0,m)$的整数的映射关系。
其中二进制串的反转后翻转和原串视为本质相同。一共有$m$种本质不同的串。要求自己的$encode/decode$不矛盾。
在$encode/decode$分别开始前都会告知你$n$的大小。此外不允许数据传输。$n \le 60$
如果是奇数，那么一个串操作后与自己一定不同，所以每两个串互相配对。$m=2^{n-1}$
此时建立映射的方法就是：如果二进制串的第$\frac{n+1}{2}$位是$1$那么对整串操作一下，然后状压剩下位即可。
如果是偶数，有些串操作后与自身完全相同。
那么我们发现，我们从外到内依次剥掉首尾两位：
如果这两位不一样，那么这两位操作后不会变。
如果一直剥到底也都不一样，那么这个串就与自己翻转同构，可见这样的串有$2^{\frac{n}{2}}$个。
否则遇到相同的一位，操作后两位都要取反，如果两个数都是$1$那我们就操作一下变成都是$0$，这样本质相同的串就有了唯一表示。
我们可以对于每个串，它有两个关键字来区分：$i$表示在上述操作中能剥掉几位。
然后整个串是$aaa0bbbbbbbb0aaa$这样的形式。其中$a$部分的长度就是$i$。左右两边的$a$是相对的。
然后只要我们知道$(i,aaabbbbbbbb)$就能唯一的确定这个串。
所以我们可以枚举$i$。设$f(i)$表示$a$部分长度为$i$的串的数量，我们就可以$while(rank \ge f(i)) rank-=f(i),i++;$
得到$i$之后剩下的$rank$值就是$aaabbbbbbbb$的状压表示。可以建立映射了。
由字符串得到排名那就更简单了。
1 #include<bits/stdc++.h>
2 using namespace std;
3 class Entropy{
4 public:
5 int N;long long zd;
6 long long cal(int a){return 1ll<<a<<(N-a-2>>1);}
7 string chg(string s){for(int i=0;i<N;++i)s[i]=s[i]=='1'?'0':'1';reverse(s.begin(),s.end());return s;}
8 long long getM(int n){
9 N=n;
10 if(n&1)return 1ll<<n-1;
11 else{
12 zd=1ll<<n/2;
13 return (1ll<<n-1)+(1<<n/2-1);
14 }
15 }
16 string encode(long long s){
17 string a="";a.resize(N);
18 if(N&1){
19 a[N>>1]='0';
20 for(int i=0;i<N>>1;++i)if(s&1ll<<i)a[i]='1';else a[i]='0';
21 for(int i=(N>>1)+1;i<N;++i)if(s&1ll<<i-1)a[i]='1';else a[i]='0';
22 // cerr<<s<<"---"<<a<<endl;
23 return a;
24 }else{//cerr<<s<<' ';
25 if(s<zd){
26 for(int i=0;i<N/2;++i)a[i]=s&1ll<<i?'1':'0',a[N-1-i]=s&1ll<<i?'0':'1';
27 //cerr<<a<<endl;
28 return a;
29 }else{s-=zd;
30 int A=0,b;
31 while(cal(A)<=s)s-=cal(A),A+=2;//cerr<<A<<' ';
32 b=N-2-A>>1;
33 for(int i=0;i<b;++i)a[i]=s&1ll<<i?'1':'0',a[N-i-1]=s&1ll<<i?'0':'1';
34 a[b]=a[N-1-b]='0';
35 for(int i=b+1;i<b+A+1;++i)a[i]=s&1ll<<i-1?'1':'0';
36 //cerr<<a<<endl;
37 return a;
38 }
39 }
40 }
41 long long decode(string s){
42 if(N&1){//cerr<<s<<"---"<<endl;
43 if(s[N>>1]=='1')s=chg(s);
44 long long ans=0;
45 for(int i=0;i<N>>1;++i)if(s[i]=='1')ans|=1ll<<i;
46 for(int i=(N>>1)+1;i<N;++i)if(s[i]=='1')ans|=1ll<<i-1;
47 // cerr<<s<<"---"<<ans<<endl;
48 return ans;
49 }else{//cerr<<s<<' ';
50 string t=chg(s);long long ans=0;
51 if(s==t){
52 for(int i=0;i<N>>1;++i)if(s[i]=='1')ans|=1ll<<i;
53 //cerr<<ans<<endl;
54 return ans;
55 }else{ans=zd;
56 int b=0,A;
57 while(s[b]!=s[N-b-1])b++;
58 if(s[b]=='1')s=t;
59 A=N-b*2-2;
60 for(int i=0;i<A;i+=2)ans+=cal(i);
61 for(int i=0;i<b;++i)if(s[i]=='1')ans+=1ll<<i;
62 for(int i=b+1;i<b+A+1;++i)if(s[i]=='1')ans+=1ll<<i-1;
63 //cerr<<ans<<endl;
64 return ans;
65 }
66 }
67 }
68 };
69 #include "entropy.h"
View Code