Yandex.Algorithm 2014 Round 1 D問題 - Splitting Money

Source

Yandex.Algorithm 2014
Yandex.Algorithm 2014 Round 1
問題文

問題概要

$N$ 枚のお札が有り,お札 $k$ の価値は $A_k$ である.
各お札について,人Xに渡すか,人Yに渡すか,誰にも渡さずに捨てるかとして,お札を分配する.
それぞれの人が $1$ 枚もお札を受け取らない場合も可.
人Xが受け取ったお札の価値の ${\rm XOR}$ と,人Yが受け取ったお札の価値の ${\rm XOR}$ が等しくなるような分配の仕方は何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

解法

$x = y$ と $x\ {\rm XOR}\ y = 0$ は同値なので,どちらかの人に渡されたお札の価値の ${\rm XOR}$ が $0$ であれば,どのように分配しても,人Xが受け取ったお札の価値の ${\rm XOR}$ と人Yが受け取ったお札の価値の ${\rm XOR}$ は等しくなる.
よって,(何枚目のお札まで分配し終わったか,どちらかに渡したお札の ${\rm XOR}$)を状態とし,そのようなパターン数をDPで計算すれば良い.
時間計算量 $O(N A_k)$.

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

#define MD 1000000007

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

#define MX 16384

int N, A[20000];
ll dp[20000], nx[20000];

int main(){
  int i, j, k;
  int rank;

  reader(&N);
  rep(i,N) reader(A+i);

  dp[0] = 1;
  REP(i,1,MX) dp[i] = 0;

  rep(k,N){
    rep(i,MX) nx[i] = dp[i];
    rep(i,MX) if(dp[i]){
      nx[i^A[k]] = (nx[i^A[k]] + dp[i]*2) % MD;
    }
    rep(i,MX) dp[i] = nx[i];
  }

  writer((int)dp[0], '\n');

  return 0;
}

Current time: 2017年07月23日15時34分20秒
Last modified: 2014年06月25日20時35分24秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: