# TopCoder SRM 663 Div2 Problem 1000 - CheeseRolling (状压dp)

Sep 22, 2015

## 题意 ##

n个人，每个人对上谁都有胜负。现在问如何安排比赛，输出每个人最后的胜利的情况数。

## 思路 ##

TC的官方题解

 What we can do is represent this as f(i,S), where i is the player in question and S the set of players available in this tournament. We want to play with recursion so we need a way to divide the problem into smaller versions of this problem. Consider this: An elimination tournament of 16 players can be seen as two tournaments of 8 distinct players each plus a last match between the winners of the two smaller tournaments. When given S players, we want to divide them in two disjoint halves: S1 and S2, the only thing we’ll know about the order is that players in S2 will be ordered after S1. So S1 and S2 will each have one winner. We are interested in scenarios in which player i wins S1 or S2 (Depending of which one i was included in). There are two cases, in one of the cases i is in S1; There are f(i,S1) ways in which i will win S1. For each j in S2, it is possible that j wins the mini-tournament of S2 a total of f(j,S2) times. If according to our match up rules, i wins after matched against j, then we need to add f(i,S1)×f(j,S2) to the final result, because those are the number of ways in which i versus j is the final match in the tournament AND thus ways in which i wins. Consider the cases in which i is in S2. Due to symmetry, this will look exactly the same, so in fact we should be adding 2×f(i,S1)×f(j,S2) to the result.

## 代码 ##

class CheeseRolling {
public:
LL dp[(1<<17)][17], number_in_state[(1<<17)];
vector<long long> waysToWin(vector<string> wins) {
int n = SZ(wins);
for (int i = 1; i < (1<<n); i++)
{
vector<int> cur_state;
for (int j = 0; j < n; j++) if ((i>>j)&1)
cur_state.push_back(j);
int sz = SZ(cur_state);
number_in_state[i] = sz;
if (sz == 1) dp[i][cur_state[0]] = 1;
if (sz != 2 && sz != 4 && sz != 8 && sz != 16) continue;
for (int s = (i-1)&i; s; s = (s-1)&i)
{
if (number_in_state[s] != sz / 2) continue;
vector<int> substate, remain_person;
for (int j = 0; j < n; j++) if ((s>>j)&1)
substate.push_back(j);
for (int j = 0; j < n; j++) if (!((s>>j)&1) && ((i>>j)&1))
remain_person.push_back(j);
int ss = i^s;
for (auto u : substate)
for (auto v : remain_person)
{
if (wins[u][v] == 'Y') dp[i][u] += dp[s][u] * dp[ss][v];
else dp[i][v] += dp[s][u] * dp[ss][v];
}
}
}
vector<LL> ans;
for (int i = 0; i < n; i++) ans.push_back(dp[(1<<n)-1][i]);
return ans;
}
};