Combination of Number Sequences

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070

AC Code

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3999614#1

分類

Bit DP

参考

http://ei1333.blogspot.com/2014/01/aoj0068-enclose-pins-with-rubber-band.html

解法

// i : 何個使ったか
// j : すでに使った数字のフラグ
// k : 作りたい値
ll dp[11][1024][331];

void reset(){
  rep(i, 11){
    rep(j, 1024){
      rep(k, 331){
        dp[i][j][k] = -1; // unused flag
      }
    }
  }
}

ll n;

// cnt : 今まで使った回数
// f : 使った数字(フラグで管理)
// sum : 作りたい値
ll rec(ll cnt, ll f, ll sum){
  if(sum<0){
    debug("can't make");
    return 0;
  }
  if(cnt==n){
    // もう選べない
    if(sum==0){
      debug("select end", sum==0);
      return 1;
    }else{
      debug("select end", sum==0);
      return 0;
    }
  }
  if(dp[cnt][f][sum]!=-1){
    debug("already memo");
    return dp[cnt][f][sum]; // メモがすでにある
  }

  ll ret = 0;
  rep(i, 10){
    // 次の値としてiを選ぼうとする
    if(((f>>i)&1)==0){
      ret += rec(cnt+1, f|(1<<i), sum - i * (cnt+1));
    }
  }
  return dp[cnt][f][sum] = ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll s;
    while(cin >> n >> s){
      reset();
      ll ans = rec(0, 0, s);
      p(ans);
    }
    
    return 0;
}