蓝桥杯2021国赛-异或三角

题目链接

因为 a ⊕ b ⊕ c = 0 a⊕b⊕c=0 a⊕b⊕c=0， a 、 b 、 c a、b、c a、b、c 互不相等，同时每位上 1 1 1 的个数为 0 0 0 或 2 2 2。设 n ≥ a > b > c ≥ 1 n≥a>b>c≥1 n≥a>b>c≥1，那么对每一位来讲， ( 1 , 1 , 0 ) (1,1,0) (1,1,0) 先于 ( 1 , 0 , 1 ) (1,0,1) (1,0,1) 出现。

再考虑能组成三角形，意味着必须存在一组 ( 0 , 1 , 1 ) (0,1,1) (0,1,1)，因为 a = b ⊕ c , a < b + c = > b ⊕ c < b + c a=b⊕c,a b⊕cb⊕c

那么可以以枚举a、c，同时设一个状态保证 ( 1 , 1 , 0 ) (1,1,0) (1,1,0) 先于 ( 1 , 0 , 1 ) (1,0,1) (1,0,1) 出现，具体见代码注释

#include
#define LL long long
using namespace std;
int T,n;
LL f[39][2][2][2][2];
LL dfs(int a,int c,int i,int j,int k)
{
	if(i==-1) return k;
	if(f[i][j][k][c][a]!=-1) return f[i][j][k][c][a];
	int top=(j?((n>>i)&1):1);
	LL res=0;
	for(int bt=0;bt<=top;bt++)
	{
		int nj=(j&&(bt==top));
		if(!bt)
		{
			res+=dfs(a,c,i-1,nj,k); //全0 
			if(c!=0) res+=dfs(a,1,i-1,nj,1); //给b、c，若c==0，给b、c的话会使b>a  
		}
		else
		{
			if(!a) res+=dfs(1,c,i-1,nj,k); //a最大，最高位1给a和b 
			else
			{
				res+=dfs(1,c,i-1,nj,k); //给a、b 
				res+=dfs(1,1,i-1,nj,k); //给a、c 
			}
		}
	}
	return f[i][j][k][c][a]=res;
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		memset(f,-1,sizeof(f));
		cout<