在 \(S=[1,n]\cap \mathbb Z\) 中选出一个最大子集 \(T\) 使得其任意两元素差不为 \(x\) 且不为 \(y\)，求 \(|T|\)。\(n\le 10^9,x,y\le 22\)。
通项，打表找规律套结论，或者矩乘。都是错的。考虑一个周期性。
注意到有 \(n=x+y\) 的包。上结论，将对于 \([1,l=x+y]\) 求出的子集 \(T'\) 复制 \(\lceil\frac nl\rceil\) 遍，就是所求答案。
\[T=\{k(x+y)+u,u\in T'\}
\]
这个太显然了。最优性显然。可达性，你考虑最终拼出来一个 0/1 串 \(a\) 表示每个数选或不选，有 \(a_i=a_{i-x-y}\)，上一个周期规定了 \(a_{i-x-y}\operatorname{nand} a_{(i-x-y)+x}\)，自然有 \(a_{i}\operatorname{nand}a_{i-y}\)。
然后问题就变成了求解 \(n=x+y\) 并输出方案（因为有 \(n\bmod l\) 的余数）。
可以状压。用刷表法。\(\mathcal O\left((x+y)2^{\max(x,y)}\right)\)。
或者搜索。注意到 \(n=44\) 是搜不出来的，我考场上过不输出方案的包靠的是打表。
这里要求存方案（前缀和）需要 \(\Theta(x^3)\) 的空间，算上逗号的话代码长度不一定够。
不过题解区有一个神奇的只搜到 \(\min(x,y)\) 的做法。
void dfs(int now){
if(now==x+1){
memcpy(b,a,sizeof(a));
for(int i=x+1;i<=x+y;i++)
if(!b[max(i-x,0)]&&!b[max(i-y,0)]) b[i]=1;
for(int i=1;i<=x+y;i++)
b[i]=b[i-1]+b[i];
ans=max(ans,(n/(x+y))*b[x+y]+b[n%(x+y)]);
return;
}
a[now]=true;
dfs(now+1);
a[now]=false;
dfs(now+1);
}
就是对于 \(i>\min(x,y)\) 全部贪心构造。不知道为什么是对的。