[ABC217] F - Make Pair

[Q] https://atcoder.jp/contests/abc217/tasks/abc217_f
DPで数え上げそうだけど、うまく切り分けられなかった。

・もし全員仲良しだったら？
N=1 (01): {01} で1通り
N=2 (0123): {01->23, 12->03, 23->01} の3通り
N=3 (012345): 01をとれば2345は3通り。それが{01, 12, 23, 34, 45} の5通りあるから5*3 = 15通り
N=4なら 7*5*3=105通り
3*5*7*9*...で構成されそう。

・N=4 ( 01234567 )のうち、もし02をとる場合、
-1-34567
この後、どう頑張っても1がとれなくなってしまう。
とるなら偶数間隔と観察できる。

DP[ 開始 ][ 終端 ] = 組み合わせ数として、
(開始は閉区間、終端は開区間。0123 = DP[0][4] )
N=4のとき、答えはDP[0][8] ( 01234567の組み合わせ )を知りたいと思う。
開始点を固定すると、01, 03, 05, 07の4通りで数えあげられる。

・01をとる場合
// DP[0][8] += DP( 234567 ) * 4C1 
DP[0][8] += DP[2][8] * 4C1

・03をとる場合
// DP[0][8] += DP( 12 ) * DP( 4567 ) *  4C2 
DP[0][8] += DP[1][3] * DP[4][8] *  4C2 

・05をとる場合
// DP[0][8] += DP( 1234 ) * DP( 67 ) * 4C3
DP[0][8] += DP[1][5] * DP[6][8] * 4C3

・07をとる場合
// DP[0][8] += DP( 123456 ) * 4C4
DP[0][8] += DP[1][7] * 4C4

Q. 4C1 ?
A.
01をとる場合、01から1つ、234567から3つとるので、4C1通り
ABBB BABB BBAB BBBA。Aが01から。Bが234567のとる順番。
234567の取り方のバリエーションはDP[2][8]に含まれるから、それは4C1とは無関係。(45->36->27とか、23->45->67とかはDP[2][8])
03をとる場合、0123から2つ、4567から2つとるので、4C2通り
05をとる場合、012345から3つ、67から1つとるので、4C3通り
07をとる場合、01234567から4つとるので4C4通り

もう1段思考整理する。

・01をとる場合
// DP[0][8] += DP( 234567 ) * 4C1
DP[0][8] += DP[2][8] * 4C1

Q. DP[2][8]は？
A. 234567を考える。

(8-2)/2 = 3ペアあるので、
2を開始点として、23,25,27の3通りの数え上げを調べていく。

・23の場合 ( --4567 )
DP[2][8] += DP[4][8] * 3C1

・25の場合 ( -34-67 )
DP[2][8] += DP[3][5] * DP[6][8] * 3C2

・27の場合 ( -3456- )
DP[2][8] += DP[3][7] * 3C3

Q. nCk？
A. テンプレートをそのまま利用。今実装と切り分けて考えるといいかも。

以下実装。

// ----- nCk -----

const ll MAX = 410;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit(){
 fac[0] = fac[1]=1;
 finv[0] = finv[1]=1;
 inv[1] = 1;
 for(int i=2; i<MAX; i++){
   fac[i] = fac[i-1] * i % MOD;
   inv[i] = MOD-inv[MOD%i] * (MOD/i) % MOD;
   finv[i] = finv[i-1] * inv[i] % MOD;//逆元の階上
 }
}

ll COM(int n, int k){
 if (n<k)
   return 0;
 if (n<0 || k<0)
   return 0;
 return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

// ----- nCk -----

ll DP[410][410];
bool ok[410][410];
ll N, M;


ll dfs(ll L, ll R){ // [L, R)
 if (L==R) return DP[L][R] = 1;
 if (DP[L][R] >= 0) return DP[L][R];
 ll ret = 0;
 ll p = (R-L)/2; // 0~8なら4ペア
for(ll k=1; k<=p; ++k){ //探索ペア数 p=4だとして,k=1のとき0~2, k=2のとき0~4
  ll r = L+k*2;
  if (!ok[L][r-1]) continue; // とれないならだめ
  // 0~2をとる(01)場合、DP[1][1] * DP[2][8] * 4C1
  // 0~4をとる(0123)場合、DP[1][3] * DP[4][8] * 4C2
  // 0~6をとる(012345)場合、DP[1][5] * DP[6][8] * 4C3
  // 0~8をとる(01234567)場合、DP[1][7] * DP[8][8] * 4C4
  ll add = dfs(L+1, r-1);
  ( add *= dfs(r, R) ) %= MOD;
  ( add *= COM(p, k) ) %= MOD;
  ( ret += add ) %= MOD;
 }
 return DP[L][R] = ret ;
}

int main(){
 COMinit();
 
 cin >> N >> M;
 rep(i, 2*N+1) rep(j, 2*N+1) DP[i][j] = -1; // 0情報も必要
 rep(i, M){
   ll a, b;
   cin >> a >> b;
   --a, --b;
   ok[a][b] = true;
   ok[b][a] = true;
 }
 ll ans = dfs(0, N*2);
 cout << ans << endl;
}

https://atcoder.jp/contests/abc217/submissions/25639670