赛时糖丸了，F题没看到要取模，赛后才发现，硬控一小时。

A.ICPC Regionals

语法题，模拟即可。

void solve(){
    int n,k;
    cin >> n >> k;
    int gold = (n + 9) / 10;
    if (gold >= k) cout << "Gold Medal\n";
    else if (gold * 3 >= k) cout << "Silver Medal\n";
    else if (gold * 6 >= k) cout << "Bronze Medal\n";
    else cout << "Da Tie\n";
    
}

B.Card Game

贪心，要么全部扔掉，要么不换。

void solve(){
    int n;cin >> n;
    vector<int> a(n);
    for (int i = 0;i < n;i ++) cin >> a[i];
    cout << max(*max_element(a.begin(),a.end()),n) << "\n";
}

C. Palindrome Coloring

考虑贪心，如果原本不是回文串，则第一次删除 ，第二次删除 。

void solve(){
    string str;cin >> str;
    int ans = 1;
    for (int i = 0,j = str.size() - 1;i < j;i ++,j --){
        if (str[i] != str[j]) {
            ans = 2;
            break;
        }
    }
    cout << ans << '\n';
}

D.Digital Pairing

考虑贪心从高位开始取，检查是否能取保留之前所有位的前提下使得结果取当前位依然成立。

void solve(){
    int n;
    cin >> n;
    vector<i64> a(n*2);
    for (int i = 0;i < 2 * n;i ++) cin >> a[i];
    i64 ans = 0;
    auto check = [&](i64 val)->bool{
        int cnt = 0;
        for (int i = 0;i < n*2;i ++){
            if ((val & a[i]) == val) cnt ++;
        }
        return cnt >= n;
    };
    for (int i = 35;i >= 0;i --){
        if (check(ans | (1LL << i))) ans |= 1LL << i;
    }
    cout << ans << '\n';
}

E.Beautiful Sequence

反过来考虑，对于子序列 我们只需找到 的子序列个数即可。

然后我们用调和级数的方式去遍历 的子序列个数，减去存在 的子序列即可。

void solve(){
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 1;i <= n;i ++) cin >> a[i];
    vector<int> cnt(n+1);
    for (int i = 1;i <= n;i ++) cnt[a[i]] ++;
    Z ans = Z::Pow(2,n)-1;
    for (int i = 1;i <= n;i ++){
        int sum = 0;
        for (int j = i*2;j <= n;j += i){
            sum += cnt[j];
        }
        ans -= Z::Pow(2,sum) * (Z::Pow(2,cnt[i])-1);
    }
    cout << ans << '\n';
}

F.Bracket Counting

注意到 很小，考虑状压拼接，设 表示已选取括号串状态 下合法方案数。

此时我们可以预处理出每个括号串的阈值和选取后剩余未匹配左括号的个数。

时间复杂度为

void solve(){
    int n;
    cin >> n;
    vector<string> str(n);
    for (int i = 0;i < n;i ++) cin >> str[i];
    vector<p32> key(n);
    int B = 0,H = -1;
    for (int i = 0;i < n;i ++){
        auto &[x,y] = key[i];
        for (auto ch : str[i]){
            y += ch == '(' ? 1 : -1;
            x = min(y,x);
        }
        B += y;
        H = max(H,x);
    }
    vector<bool> vis(1 << n,0);
    vector<Z> dp(1 << n);
    auto dfs = [&](auto&& self,int st,int w)->Z{
        if (w < 0) return 0;
        if ((st == (1 << n) - 1)) return w == 0;
        if (vis[st]) return dp[st];
        Z res = 0;
        for (int i = 0;i < n;i ++){
            int d = 1 << i;
            if (st & d) continue;
            if (w + key[i].first < 0) continue;
            res += self(self,st | d,w + key[i].second);
        }
        vis[st] = 1;
        return dp[st] = res;
    };
    cout << dfs(dfs,0,0) << "\n";
}