符号三角形问题
class Triangle {
friend int Compute(int);
private:
void Backtrack(int t);
int n, half, count, **p;
long sum;
};
void Triangle::Backtrack(int t) {
if ((count > half) || (t * (t - 1) / 2 - count > half)) {
return;
}
if (t > n) {
sum++;
} else {
for (int i = 0; i < 2; i++) {
p[1][t] = i;
count += i;
for (int j = 2; j <= t; j++) {
p[j][t - j + 1] = p[j - 1][t - j + 1] ^ p[j - 1][t - j + 2];
count += p[j][t - j + 1];
}
Backtrack(t + 1);
for (int j = 2; j <= t; j++) {
count -= p[j][t - j + 1];
}
count -= i;
}
}
}
int Compute(int n) {
Triangle X;
X.n = n;
X.count = 0;
X.sum = 0;
X.half = n * (n + 1) / 4;
if (X.half % 2 == 1) {
return 0;
}
X.half /= 2;
int **p = new int*[n + 1];
for (int i = 0; i <= n; i++) {
p[i] = new int[n + 1];
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
p[i][j] = 0;
X.p = p;
X.Backtrack(1);
return X.sum;
}
最后更新:
2024年1月14日 18:59:58
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42