ABC041 徒競走
結構まえに解いた問題が好きだったので書く。
1~Nまでの番号のついたウサギが徒競走し、x番目がy番目より早く着くという情報がM個与えられる。
その情報にあうような着順が何通りあるか求める問題。
制約をみると1<=N<=16であったのですぐにbitDPを思いついた。
しかし僕はDPができないのでメモ化再帰をする。(弱い)
#include<bits/stdc++.h> #define int long long #define PB push_back #define FI first #define SE second using namespace std; typedef pair<int,int> PII; static const int inf = 1ll<<60; static const int MAX_N = 16; static const int MBIT = 1<<17; int N; int M; int all; int mem[MBIT]; vector<int> V[MAX_N+1]; int cal(int bit){ int res=0; if(mem[bit]!=-1)return mem[bit]; if(bit==0)return 1; for(int i=1;i<=N;++i){ bool is=false; int b=1<<i; for(int j=0;j<V[i].size();++j){ int k=1<<V[i][j]; if(!(k&bit)){ is=true; break; } } if(is)continue; if(bit&b){ res+=cal(bit-b); } } return mem[bit]=res; } signed main(){ memset(mem,-1,sizeof(mem)); cin>>N>>M; for(int i=1;i<=N;++i)all+=pow(2,i); for(int i=0;i<M;++i){ int x,y; cin>>x>>y; V[x].PB(y); } int ans=0; ans=cal(all); cout<<ans<<endl; }