CFR 389 D. Fox and Minimal path ( Binary Enumeration )

題意：
給 K，求一個無向圖鄰接矩陣，使得節點 1 到節點 2 的最短路徑恰有 K 個。

資料規模：
1 ≤ K ≤ 1e9
輸出的圖的節點數 ≤ 1000

解法：
考慮二進制枚舉，需要 *2 就往右連一個菱形，需要 +1 就從節點 1 連到當前的終點。

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

const int MAXN = 1000;

int K;
int G[ MAXN ][ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> K;
  if( K == 1 ){
    cout << 2 << endl;
    cout << "NY" << endl;
    cout << "YN" << endl;
    exit( 0 );
  }
  queue< int > que;
  for( int i = 2; i < MAXN; ++i ){
    que.emplace( i );
  }
  int f = 0;
  for( int i = 31 - __builtin_clz( K ) - 1, len = 2 ; i >= 0; len += 2, --i ){
    int u = que.front(); que.pop();
    int d = que.front(); que.pop();
    int m = 1; if( i > 0 ) m = que.front(), que.pop();
    G[ f ][ u ] = G[ u ][ f ] = 1;
    G[ f ][ d ] = G[ d ][ f ] = 1;
    G[ u ][ m ] = G[ m ][ u ] = 1;
    G[ d ][ m ] = G[ m ][ d ] = 1;
    f = m;
    if( K >> i & 1 ){
      int p = 0;
      for( int j = 0; j < len - 1; ++j ){
        int nxt = que.front(); que.pop();
        G[ p ][ nxt ] = G[ nxt ][ p ] = 1;
        p = nxt;
      }
      G[ p ][ f ] = G[ f ][ p ] = 1;
    }
  }
  cout << MAXN << endl;
  for( int i = 0; i < MAXN; ++i ){
    for( int j = 0; j < MAXN; ++j ){
      cout << "NY"[ G[ i ][ j ] ];
    }
    cout << "\n";
  }
  return 0;
}