#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,h,w;
ll dp[(1<<20)];
vector<int> v[20];
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;cin>>x>>y;x--;y--;
v[y].push_back(x);
}
dp[0]=1;
for(int i=0;i<(1<<(n+1));i++){
if(dp[i]==0)continue;
for(int bit=0;bit<n;bit++){
if(i&(1<<bit))continue;
else{
bool flag=1;
for(int j=0;j<(int)v[bit].size();j++){
if(i&(1<<v[bit][j]))continue;
else flag=0;
}
if(flag)dp[i|(1<<bit)]+=dp[i];
}
}
}
cout<<dp[(1<<n)-1]<<endl;
return 0;
}
- どうやってやるのかなーって考えてる時に bitdpするっていう選択肢を考えなかったのが辛い。
- 一瞬解説をみて bitdpだとわかったので、それからは自分で考えてやった。
- k- bit目が0なら k+1番のウサギはまだゴールしてない、1ならゴールしてると考えてやる。
- 先にゴールしていてほしいウサギが全部ゴールしているなら、着目しているウサギもゴールさせて良い。
- そんな感じで最後は全員ゴールした状態の通り数なので、全ての bitが1のdp配列を見れば良い。
- 制約に16があったら bitdpを疑おうね自分!!!!