daily 1

CF 1679F
参考了这篇题解(https://www.cnblogs.com/zhiyangfan/p/16276097.html)

先处理出(j,k)j在前面和在后面不允许出现的数字

然后dp[i][sta]表示当前选择到地i个数，不允许出现的数的状态为sta的等价类个数

然后根据j在前面和后面计算出当前转移的sta

void solve(){
  int n,m;
  cin>>n>>m;
  vector dp(n+1,vector<int>(1<<10));
  vector<int> a(1<<10),b(a);//a[i] means (i,*) b[i] means (*,i)
  for(int i=1;i<=m;++i){
    int u,v;
    cin>>u>>v;
    a[u]|=(1<<v);
    b[v]|=(1<<u);
  }
  dp[0][0]=1;
  for(int i=1;i<=n;++i){
    for(int sta=0;sta<(1<<10);++sta){
      for(int j=0;j<10;++j){
        if(sta&(1<<j))continue;//we could not pick some digit which could be placed earlier
        (dp[i][(sta&a[j])|b[j]]+=dp[i-1][sta])%=MOD;
      }
    }
  }
  int ans=0;
  for(int sta=0;sta<(1<<10);++sta){
    ans=(ans+dp[n][sta])%MOD;
  }
  cout<<ans<<'\n';
  return;
}