SRM566 Div1 Easy

250

ある1頂点だけから複数本の辺が出ている
辺が1つしかない
辺が1つもない
ある3頂点が3辺で結ばれている。

の4パターンを数える。

const int M = 60;
lli nCk[M][M];

void f(void)
{
  for (int i = 0; i < M; ++i) {
    nCk[i][i] = nCk[i][0] = 1;
  }
  for (int i = 0; i < M; ++i) {
    for (int j = 1; j < i; ++j) {
      nCk[i][j] = nCk[i - 1][j - 1] + nCk[i - 1][j];
    }
  }
  return ;
}

class PenguinSledding {
public:
  long long countDesigns(int numcp,
                         vector <int> cp1,
                         vector <int> cp2)
  {
    f();

    const int N = numcp;
    vector<int> g[N];

    for (int i = 0; i < cp1.size(); ++i) {
      --cp1[i];
      --cp2[i];
    }

    bool adj[M][M];
    fill(&adj[0][0], &adj[M - 1][M - 1] + 1, false);

    for (int i = 0; i < cp1.size(); ++i) {
      g[cp1[i]].push_back(cp2[i]);
      g[cp2[i]].push_back(cp1[i]);
      adj[cp1[i]][cp2[i]] = adj[cp2[i]][cp1[i]] = true;
    }

    lli sum = cp1.size() + 1; // 1-edge, no-edge

    for (int i = 0; i < N; ++i) {
      for (int j = 2; j <= g[i].size(); ++j) {
        sum += nCk[g[i].size()][j];
      }
    }

    for (int i = 0; i < N; ++i) {
      for (int j = i+1; j < N; ++j) {
        for (int k = j+1; k < N; ++k) {
          if (adj[i][j] && adj[j][k] && adj[k][i]) ++sum;
        }
      }
    }

    return sum;
  }
};