# Problem I

## 題目簡述

<!-- 有 $2n$ 個空位排成一排，現在想要將 $1$ 到 $n$ 每個數字各兩次填入這些空位。
現在已經有部分數字被排入空位了，請問有多少種方法，能將剩餘的數字填入空位後，任何兩個相同的數字皆不相鄰？ -->

在一排中有 $2n$ 個空位，我們的目標是將 $1$ 到 $n$ 的數字各填入兩次。有些空位已經被填入了數字。現在的問題是，在剩下的空位中，有多少種方法可以填入數字，使得任何兩個相同的數字都不相鄰？

## 解題參考

我們可以利用[排容原理](https://zh.wikipedia.org/zh-tw/%E6%8E%92%E5%AE%B9%E5%8E%9F%E7%90%86)加上動態規劃來解決這道題目。

對於集合 $S\subseteq [n]$，我們定義 $f(S)$ 為所有將剩餘數字填入空位的方法中，對於所有的數字 $i\in S$，兩次 $i$ 出現的位置相鄰的情形總數。那麼我們所求之數即為 $\sum_{S\subseteq [n]} f(S)(-1)^{|S|}$。

枚舉所有的子集合 $S$ 得花上 $\Omega(2^n)$ 的時間，以 $n\le 100$ 的測資範圍來說，是會 TLE 的，因此我們得需要加上額外的觀察。比如說：當集合大小 $|S|$ 固定為 $k$ 時，我們能否快速算出 $\sum_{|S|=k} f(S)$ 之值？若此時所有的 $f(S)$ 皆相等，那麼顯然挑其中一個來算、再乘上 ${n\choose k}$ 就能得到總和。遺憾的是，就算集合大小 $|S|$ 相同，$f(S)$ 仍可能有不同之值，其原因是這排空位中已經有些位置早已填入數字了。

幸運的是，對於早已『部分填入空位』的數字們 (不妨定義為集合 $X$)，我們發現 $f(S)$ 的值僅與『有多少 $X$ 內的數字被選入 $S$』與『被選入後這些數字有幾種放法』有關。因此，這時候我們只需要利用動態規劃，定義 $dp[\ell][x][y]$ 為：目前做到輸入序列的第 $\ell$ 個元素、在這之前我們已選定 $x$ 個部分出現的數字被加入 $S$ 中、且我們也從未出現的數字中選了 $y$ 個加入 $S$ 中並指定了它們的位置後，這 $2(x+y)$ 個數字在前 $\ell$ 個空位中有幾種放法。

從 $dp[\ell]$ 到 $dp[\ell+1]$ 的轉移也就比較明瞭了：如果輸入之第 $\ell$ 與 $\ell+1$ 這兩格初始都是空的，那麼我們可以同時指派一個未出現的數字給這兩格位置 (也就是增加了 $y$ 的數量)：

$$dp[\ell+1][x][y]\gets dp[\ell][x][y] + dp[\ell-1][x][y-1]$$

若兩格其中一格已經有某個只出現一次的數字、另一格為空，那麼就可以考慮該數字要不要加入 $S$：

$$dp[\ell+1][x][y]\gets dp[\ell][x][y] + dp[\ell-1][x-1][y]$$

由於轉移所需要的時間皆為常數。因此，我們就能得到一個 $O(n^3)$ 時間複雜度的演算法啦～
最後要怎麼從 $dp[2n]$ 表格算出 $\sum_{|S|=k} f(S)$ 之值呢？注意到 $dp$ 後面兩個參數代表被選入 $S$ 的數字個數，因此 $x+y=k$。而使用了 $x$ 個已出現的數字、加上使用了 $2y$ 未出現的數字後，唯一決定了剩下的空位總數，所以此時只需要乘上剩餘數字的排列數即可 (記得去掉重複計算的部分，每組尚未出現的數字都需要除以 $2$)。

(備註：狀態的設計其實有很多種，不過大部分都會得到 $O(n^3)$ 的時間複雜度。不曉得有沒有 $O(n^2)$ 的解法？)

## 參考程式碼

#include <bits/stdc++.h>
using namespace std;


const int MOD = 1e9+7;
long long C[205][205] = {}, F[205]={}, TWO[205] = {};
void add(int &x, int v) {
  x += v;
  if (x >= MOD) x -= MOD;
  return;
}
long long EXTGCD(long long x, long long y) {
  long long p=1, q=0, r=0, s=1;
  while (y != 0) {
    long long w=x/y;
    x=x%y;
    p-=w*r;
    q-=w*s;
    swap(x, y);
    swap(p, r);
    swap(q, s);
  }
  return p;
}
long long INV(long long val) {
  return EXTGCD(val, MOD);
}

void solve() {
  int n;
  scanf("%d", &n);
  vector<int> a(2*n);
  vector<int> occur(n+1, 0);
  for(int i=0;i<2*n;i++) scanf("%d", &a[i]);
  for(int i=0;i<2*n;i++) occur[a[i]]++;
  int m1 = 0, m0 = 0;
  for(int i=1;i<=n;i++) {
    if(occur[i]==1) ++m1;
    if(occur[i]==0) ++m0;
  }
  int dp[3][105][105]={};
  dp[0][0][0] = 1;
  dp[1][0][0] = 1;
  int u=1,u1=0,u2=2;
  for (int l=1;l<2*n;l++) {
    swap(u1,u2);
    swap(u,u1);
    memcpy(dp[u], dp[u1], sizeof(dp[u]));
    
    if (a[l]==0 && a[l-1]==0) {
      for(int i=1;i<=m0;i++)
        for(int j=0;j<=m1;j++) {
          add(dp[u][i][j], dp[u2][i-1][j]);
        }
    } else if ((a[l] == 0 && occur[a[l-1]] == 1) ||
              (a[l-1]==0 && occur[a[l]] == 1)) {
      for(int i=0;i<=m0;i++)
        for(int j=1;j<=m1;j++) {
          add(dp[u][i][j], dp[u2][i][j-1]);
        }
    }
  }
  long long answer = 0;
  for(int i=0;i<=m0;i++)
    for(int j=0;j<=m1;j++) {
      long long tmp = C[m0][i] * F[i] % MOD * dp[u][i][j] % MOD * F[2*(m0-i) + (m1-j)] % MOD * TWO[m0-i] % MOD;
      
      if ((i+j)%2==0) {
        answer += tmp;
      } else {
        answer += (MOD - tmp);
      }
    }
  answer %= MOD;
  printf("%lld\n", answer);
  return;
}

int main() {
  int T;
  
  C[0][0] = 1;
  for (int i=1;i<=200;i++) {
    C[i][0] = 1;
    for(int j=1;j<=i;j++) {
      C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
    }
  }
  F[0] = F[1] = 1;
  for(int i=2;i<=200;i++) F[i] = F[i-1] * (long long) i % MOD;
  TWO[0] = 1;
  for(int i=1;i<=200;i++) TWO[i] = TWO[i-1] * 2 % MOD;
  for(int i=1;i<=200;i++) TWO[i] = (INV(TWO[i]) % MOD + MOD)%MOD;

  scanf("%d", &T);
  while(T--) solve();
  return 0;
}