CFR 285 D. Permutation Sum ( Meet in the Middle, Search )

Problem - D - Codeforces

題意：
問有多少 A, B, C 數列的組合，使得 ( A[ i ] + B[ i ] ) % N = C[ i ]，且 A, B, C 都是 [ 0, N ) 的排列。

資料規模：
The single line contains integer n (1 ≤ n ≤ 16).
TL: 1500 ms
ML: 256 MB

解法：
有用到這題的結論，那就是只有排列長度為奇數的時候解會是非零。接著可以考慮亂搜索打表，但是這裡用中途相遇法的技巧直接搜出答案。由於時間開得特別緊，所以手動將前半所有可能的子集合的表示法對應到 0 開始的正整數，至多只需要 C( 15, 7 ) = 6435 的空間。另一個小技巧是將 A 陣列固定為 { 0, 1, 2, .. N - 1 } 這樣的排列，做完之後可以直接對應 N! 種解。

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

const int MOD = ( int ) 1e9 + 7;

int N;
int mp[ 1 << 15 ];
int dp[ 6500 ][ 6500 ];

void pre_dfs( int x, int s, int t ){
  if( x == N / 2 ){
    ++dp[ mp[ s ] ][ mp[ t ] ];
    return;
  }
  for( int y = 0; y < N; ++y ){
    if( s >> y & 1 ) continue;
    if( t >> ( x + y ) % N & 1 ) continue;
    pre_dfs( x + 1, s | 1 << y, t | 1 << ( x + y ) % N );
  }
}

void dfs( int x, int s, int t, int &ans ){
  if( x == N ){
    ( ans += dp[ mp[ ( 1 << N ) - 1 ^ s ] ][ mp[ ( 1 << N ) - 1 ^ t ] ] ) %= MOD;
    return;
  }
  for( int y = 0; y < N; ++y ){
    if( s >> y & 1 ) continue;
    if( t >> ( x + y ) % N & 1 ) continue;
    dfs( x + 1, s | 1 << y, t | 1 << ( x + y ) % N, ans );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  if( ~N & 1 ){
    cout << 0 << endl;
    exit( 0 );
  }
  for( int s = 0; s < 1 << N; ++s ){
    if( __builtin_popcount( s ) != N / 2 ) continue;
    static int cnt = 0;
    mp[ s ] = cnt++;
  }
  int ans = 0;
  pre_dfs( 0, 0, 0 );
  dfs( N / 2, 0, 0, ans );
  for( int i = 1; i <= N; ++i ){
    ans = 1LL * ans * i % MOD;
  }
  cout << ans << endl;
  return 0;
}