https://projecteuler.net/problem=434

http://mathworld.wolfram.com/RigidGraph.html
https://en.wikipedia.org/wiki/Structural_rigidity
http://www.johannesbader.ch/2013/09/project-euler-problem-434-rigid-graphs/

//}/* .................................................................................................................................. */

const int N = int(1e3) + 9;
Int fact[N], B[N][N];
int n;

Int binom(int n, int m){
    if (n<m) return 0;
    return fact[n] / fact[m] / fact[n-m];
}

Int b(int a, int b){
    if (a >= b) return B[a][b];
    return B[b][a];
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    n = 100; fact[0] = 1; REP_1(i, n) fact[i] = fact[i-1] * i;
    Int z = 0;

    REP_1(i, n){
        B[i][0] = i == 1 ? 1 : 0;
        REP_1(j, i){
            B[i][j] = pow(2, i*j);
            REP_1(ii, i) FOR_1(jj, 0, j){
                if (i == ii && j == jj) break;
                B[i][j] -= binom(i-1, ii-1) * binom(j, jj) * b(ii, jj) * pow(2, (i-ii)*(j-jj));
            }
            z += B[i][j];
            if (i != j) z += B[i][j];
        }
    }

    cout << z << endl;
}

Posted by xiaodao
Category: PE