940 C. How Does the Rook Move?（dp）

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 3e5+10 ,M = 1e9 + 7 ;
 
int dp[N]  ;
int t , n , q ;
 
int main(){
  cin >> t ;
  while(t  --){
    memset(dp,0,sizeof(dp)) ;//每一次进行清零 
    cin >> n >> q ;
    int ans = 0 ;
    while(q --){
      int x , y ;
      cin >> x >> y ;
      ans += (2 - (x==y)) ;//记录我们已经用过的行和列 
    }
    dp[0] = 1 ; //初始化，当没有空余的行和列的时候我们只能等于本来的已经固定的棋子方案书
    //dp[1] = 1 ; //当只有一行一列的时候我们只能添加  i，i  这种方式  
    int m = n - ans ;
    for(int i = 2 ; i <= m ; i++){
      dp[i] =(dp[i-1] % M + ((long long)2*(i-1)*dp[i-2]) % M) %M ;
    }
    cout << dp[m] << endl ;
  }
  return 0 ;
}