読者です 読者をやめる 読者になる 読者になる

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;
}