[ABC310] D - Peaceful Teams

[Q] https://atcoder.jp/contests/abc310/tasks/abc310_d

地獄の業火に90分焼かれました。

考察
こちら間違いルート。
・10!=3628800 なので、N!*100くらいならいけそう。
・とりあえずチーム人数の分け方は求まりそう。5人を2チームにわけるのは(1, 4)と(2, 3)の2通りだなと思うが、この道はTLEルート。間違い。
・このあと、next_permutation()で探索かと思うが、これが、あっこの沼、深いッ！ボボボボボボ！！
・combination分減らすもTLE。

正解ルートはこっち。
---------------解説---------------
・1人ずつ処理する。処理は2パターンのみ。
1. 既存チームに加える
2. チームを新設する
これで、N人見終わったときにTチーム存在すれば正解パターンに加算。

実装

int main() {
  cincout();
  ll ans = 0;
  ll N, T, M;
  cin >> N >> T >> M;
  vector<ll> ng(N, 0);
  rep(i, M){
    ll a, b;
    cin >> a >> b;
    --a, --b;
    ng[b] |= (1 << a);
  }
  // 1人ずつ処理する。
  // 既存チームに加えられるなら入れる。
  // Tチームに至っていないなら新設する。
  vector<ll> teams(T, 0);
  function<void(ll, ll)> dfs = [&](ll cur, ll teamcnt) {
    if (cur == N){
      if (teamcnt == T) ++ans;
      return;
    }
    // 既存チームに加える
    rep(i, teamcnt) {
      if (teams[i] & ng[cur]) continue;
      teams[i] |= (1 << cur);
      dfs(cur + 1, teamcnt);
      teams[i] &= ~(1 << cur);
    }
    // 新設する
    if (teamcnt < T) {
      teams[teamcnt] |= (1 << cur);
      dfs(cur + 1, teamcnt + 1);
      teams[teamcnt] &= ~(1 << cur);
    }
  };
  dfs(0, 0);
  cout << ans << endl;
}

https://atcoder.jp/contests/abc310/submissions/43648573