がいずれも小さいので,全探索して数えても間に合いそう. DFS によりすべて列挙する. このとき,取りこぼしと重複が無いようにする. 今回は起こらなかったが,仮に重複するのなら,その分を割ることにする.
実装
先に 個の入れ物 を用意して,そこに人 を割り当てていく. 重複しないために, 空の が複数あってそれを使うときは, 一番 の小さい物を使うというルールにする.
また,DFS で潜る前に変更した部分を, DFS の潜りから帰った後に戻す.
終了条件と遷移を分けて書くと楽. DFS の深さ において,人 の割り当てを決める.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, t, m ;
cin >> n >> t >> m;
vll a(m), b(m);
rep(i,m){
cin >> a[i] >> b[i];
a[i]--, b[i]--;
}
vvll v(t);
ll ans = 0;
auto f = [&](auto f, ll i = 0) -> void {
if(i == n){
rep(j,t) rep(k,m){
if(in(a[k], v[j]) && in(b[k], v[j])) return;
}
rep(j,t) if(v[j].size() == 0) return;
ans++;
return;
}
bool g = false;
rep(j,t) if(!g){
if(v[j].size() == 0) g = true;
v[j].push_back(i);
f(f, i+1);
v[j].pop_back();
}
};
f(f);
cout << ans << endl;
return 0;
}