保存されている過去のバージョンの一覧

2018年02月12日18時28分47秒

「みんなのプロコン 2018」予選 D問題 - XOR XorY

Source

「みんなのプロコン 2018」予選
問題文

問題概要

$N$ 個の整数 $C_1,C_2,\ldots,C_N$ が与えられる．
また，$K \times K$ の行列 $\{A_{ij}\}_{i,j=1}^K$ と $2$ つの整数 $X,Y$ が与えられる．
$N$ 個の整数の中から $K$ 個の整数を選び数列 $a_1,a_2,\ldots,a_K$ を以下の条件を満たすように作る．

  1. 任意の$1 \leq i,j \leq K$ に対して，$a_i \oplus a_j \oplus A_{ij}$ が $X$ または $Y$ となる

ただし，$\oplus$ はビットごとに排他的論理和 (XOR) を行う演算である．
作れる数列は何通りあるかを $\mathrm{mod}\ 1000000007\ (10^9+7)$ で求める問題．
$N$ 個の整数からの選び方が異なっていても，最終的な数列 $a_1,\ldots,a_K$ が同じになるなら重複してカウントはしない．

解法

簡単のため，次のように順番に前処理をしておく．

そうすると条件は，$a_i \oplus a_j$ が $A_{ij}$ または $A_{ij} \oplus X$ となる．
ここで，任意の整数 $n$ に対して $n$ と $n \oplus X$ を同一視する．
すると，条件は $a_i \oplus a_j = A_{ij}$ となるので，$a_1$ さえ決めてしまえば，$a_2,a_3,\ldots,a_K$ は一意に定まる．
よって，全ての可能性を列挙することが可能．
しかし，実際には $a_i = n$ として，$n$ を使ったのか $n \oplus X$ を使用したのか，パターンの数を足し上げる必要があるが，これは二項係数の足し合わせで計算できる．
時間計算量はよくわからなかったけど，適当に枝刈りしながら列挙すれば十分に高速で通った．

cLay（version 20180208-1）のコード

C++に変換後のコードはこちら

int N, K, X, Y, C[2200];
int A[1100][1100];

int ok[2200];
int sz[2200][2];

int cur[2200];
int use[2200];
combination_mint comb;

inline int nrm(int x){
  if(x < (x^X)) return x;
  return x^X;
}

mint solve(int dep){
  int i, j, k, x;
  mint res, tmp;
  res = 0;
  
  if(dep==K){
    res = 1;
    rep(i,2048) use[i] = 0;
    rep(i,dep) use[cur[i]]++;
    rep(i,2048) if(use[i]){
      tmp = 0;
      rep(j,use[i]+1){
        if(j <= sz[i][0] && use[i]-j <= sz[i][1]) tmp += comb.C(use[i], j);
      }
      res *= tmp;
    }
    return res;
  }

  if(dep==0){
    rep(i,2048) if(ok[i]){
      ok[i]--;
      cur[dep] = i;
      res += solve(dep+1);
      ok[i]++;
    }
    return res;
  }

  x = nrm(A[0][dep] ^ cur[0]);
  if(ok[x]){
    rep(i,dep) if(x != nrm(A[i][dep] ^ cur[i])) break;
    if(i==dep){
      ok[x]--;
      cur[dep] = x;
      res += solve(dep+1);
      ok[x]++;
    }
  }
  return res;
}

{
  int i, j, k;
  mint res;

  comb.init(1100);
  
  rd(N,K,X,Y,C(N));
  rep(i,K) rep(j,K) rd(A[i][j]);
  rep(i,K) rep(j,K) A[i][j] ^= X;
  Y ^= X;
  X = Y;

  rep(i,K) rep(j,K) A[i][j] = nrm(A[i][j]);

  rep(i,K) if(A[i][i] != 0){
    wt(0); return 0;
  }
  rep(i,K) rep(j,i+1,K) if(A[i][j] != A[j][i]){
    wt(0); return 0;
  }

  rep(i,2048) ok[i] = 0;
  rep(i,2048) sz[i][0] = sz[i][1] = 0;
  rep(i,N){
    k = nrm(C[i]);
    ok[k]++;
    if(k==C[i]) sz[k][0]++; else sz[k][1]++;
  }

  res = solve(0);
  wt(res);
}

Current time: 2024年04月19日14時27分25秒
Last modified: 2018年02月12日18時28分47秒 (by laycrs)
Tags: Competitive_Programming AtCoder yahoo-procon2018-qual
トップページに戻る

Logged in as: unknown user (not login)

ログイン：