翻译
有0~m-1的数被分成了两个集合
每次你可以从两个集合中任取一个数做加法并对m取模
问最后0~m-1中不能被组合出来的数有多少个
会给出你A集合 大小不超过200000
m<=1e9
完了题解都看不太懂……完全不知道讲的是啥……
考虑一个数$a$，如果它不能被表示出来，那么对于每一个$xin A$，都有$(a-x)\%min A$（如果这两个数不在同一集合那么它就可以被组成了）
然后，整个序列很明显可以被分成两段，左边一段小于$a$右边一段大于$a$
如果$x<a$，那么$a-x<a$，所以两个数都在左边那一段
如果$x>a$，那么$(a-x)\%m=m+a-x$，感性理解一下它也是大于$a$的，所以两个数都在右边那一段
那么再考虑一下，以左边一段为例，设区间为$[1,r]$，$a=A[1]+A[r]$，那么必然得有$a=A[2]+A[r-1]$否则$a-A[2]$或$a-A[r-1]$肯定在$B$里面，继续下去也是。那么就是说这段区间必须回文
然后右边那段区间同理
所以我们考虑枚举$r$然后每一次判断是否两段都回文即可
然后这个回文的判定的话……看代码好了……
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #define ll long long 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 using namespace std; 9 inline int read(){ 10 #define num ch-'0' 11 char ch;bool flag=0;int res; 12 while(!isdigit(ch=getc())) 13 (ch=='-')&&(flag=true); 14 for(res=num;isdigit(ch=getc());res=res*10+num); 15 (flag)&&(res=-res); 16 #undef num 17 return res; 18 } 19 char sr[1<<21],z[20];int C=-1,Z; 20 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 21 inline void print(int x,char ch){ 22 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 23 while(z[++Z]=x%10+48,x/=10); 24 while(sr[++C]=z[Z],--Z);sr[++C]=ch; 25 } 26 const ll ha=569;const int N=210005; 27 int a[N],b[N];ll ha1[N],ha2[N],tmp[N];int gg[N],ans,n,m; 28 void init(){ 29 for(int i=1;i<n;++i) ha1[i]=ha1[i-1]*ha+b[i]; 30 for(int i=n-1;i;--i) ha2[i]=ha2[i+1]*ha+b[i]; 31 } 32 bool ok(int l,int r){ 33 return ha1[r]-ha1[l-1]*tmp[r-l+1]==ha2[l]-ha2[r+1]*tmp[r-l+1]; 34 } 35 int main(){ 36 // freopen("testdata.in","r",stdin); 37 n=read(),m=read(); 38 for(int i=1;i<=n;++i) a[i]=read(); 39 for(int i=1;i<n;++i) b[i]=a[i+1]-a[i]; 40 tmp[0]=1; 41 for(int i=1;i<=n;++i) tmp[i]=tmp[i-1]*ha; 42 init(); 43 for(int i=1;i<=n;++i){ 44 bool fl=true; 45 if(i!=1) fl&=ok(1,i-1); 46 if(i!=n){ 47 fl&=(a[1]+a[i]+m==a[i+1]+a[n]); 48 if(i!=n-1) fl&=ok(i+1,n-1); 49 } 50 if(fl) gg[++ans]=(a[1]+a[i])%m; 51 } 52 sort(gg+1,gg+1+ans); 53 print(ans,' '); 54 for(int i=1;i<=ans;++i) print(gg[i],' '); 55 Ot(); 56 return 0; 57 }