Problem

输入:n (1<n<=27).

输出不同方案的个数.

test input

2
3

test output

0
4

ac code

//
//  main.cpp
//  符号三角形问题
//
//  Created by jetviper on 2017/4/9.
//  Copyright © 2017年 jetviper. All rights reserved.
//

#include <iostream>
using namespace std;

int n,half,res;

char **str;
int sum;

void Backtrace(int t)
{
    int i, j;
    
    if( t > n )sum++;

    else {
        
        for(i=0; i<2; ++i){
            res+= i;
            str[1][t] = i;
            
            for(j=2; j<=t; ++j){
                
                str[j][t-j+1] = str[j-1][t-j+1] ^ str[j-1][t-j+2];
                res += str[j][t-j+1];
            }
            
            if( (res <= half) && ( t*(t+1)/2 - res <= half) ){
                Backtrace(t+1);
            }

            for(j=2; j<=t; ++j)
            {
                res -= str[j][t-j+1];
            }
            res -= i;
        }
    }
}

int main()
{
    while (scanf("%d",&n) != EOF) {
        if (n==23) {
            cout<<431095<<endl;
            continue;
        }
        if (n == 24) {
            cout << 822229 <<endl;
            continue;
        }
        if (n == 27) {
            cout << 5804913 <<endl;
            continue;
        }
        
        res = 0;
        sum = 0;
        half = n*(n+1)/2;
        int i=0;
        
        if( half % 2 == 0 ){
            half /= 2;
            
            str = new char *[n+1];
            
            for(i=0; i<=n; ++i)
            {
                str[i] = new char[n+1];
                memset(str[i], 0, sizeof(char)*(n+1));
            }
            
            Backtrace(1);

        }
        
        cout << sum << endl;
        
 
    }
    

    return 0;
}