题解 | GCPC总决赛

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    
    // dp[mask][diff]：mask状态下净胜场为diff的方案数
    // diff范围：-n 到 n，所以偏移n来存储
    vector<vector<ll>> dp(1 << n, vector<ll>(2 * n + 1, 0));
    dp[0][n] = 1;  // 初始：净胜场为0（偏移后为n）
    
    for (int mask = 0; mask < (1 << n); mask++) {
        int games = __builtin_popcount(mask);  // 已进行比赛数
        
        for (int diff = 0; diff <= 2 * n; diff++) {
            if (dp[mask][diff] == 0) continue;
            
            for (int j = 0; j < n; j++) {
                if (mask >> j & 1) continue;  // B选手j已使用
                
                int next_mask = mask | (1 << j);
                int new_diff = diff;
                
                if (a[games] > b[j]) {
                    new_diff = diff + 1;  // A赢，净胜场+1
                } else if (a[games] < b[j]) {
                    new_diff = diff - 1;  // B赢，净胜场-1
                }
                // 平局：净胜场不变
                
                if (new_diff >= 0 && new_diff <= 2 * n) {
                    dp[next_mask][new_diff] += dp[mask][diff];
                }
            }
        }
    }
    
    // 统计结果
    ll win = 0, lose = 0, draw = 0;
    for (int diff = 0; diff <= 2 * n; diff++) {
        if (diff > n) win += dp[(1 << n) - 1][diff];      // 净胜场 > 0
        else if (diff < n) lose += dp[(1 << n) - 1][diff]; // 净胜场 < 0
        else draw += dp[(1 << n) - 1][diff];              // 净胜场 = 0
    }
    
    cout << win << " " << lose << " " << draw << endl;
    return 0;
}