Codeforces 940 C

首先对原棋盘进行预处理，将已经下棋的对应行删除，得到一个n*n的空白棋盘。

显然如果暴力根本过不了，那么接下来就考虑纯数学方法与dp，这里介绍一下dp。

设$dp_i$为i*i的棋盘的方案数，思考$dp_{i-1},dp_{i-2}$与$dp_i$的关系。

可对$dp_i$左上角是否为空进行讨论。

若$dp_i$左上角不为空，则左上角不为空的方案数为$dp_{i-1}$，即将$dp_{i-1}$的左上角补一个棋。

若$dp_i$左上角为空，则第一行棋子的摆放可能有n-1种，相应的，第一列的棋子摆放有n-1种。

故$dp_i=dp_{i-1}+2*(n-1)dp_{i-2}$。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int t;
const int MOD=1e9+7;
long long dp[300005];
int main() {
    dp[1]=1;
    dp[0]=1;
    for(int i=2;i<=300005;i++){
        dp[i]=dp[i-1]+2*(i-1)*dp[i-2];
        dp[i]%=MOD;
    }
    cin>>t;
    while(t--){
        cin>>n>>k;
        int a,b;
        for(int i=1;i<=k;i++){
            cin>>a>>b;
            if(a==b)n--;
            else n-=2;
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}