题解归档 - cf888E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf888E
• 本地来源：problems/cf888E/idea.md
• 题目链接：https://codeforces.com/contest/888/problem/E
• 原始标题：cf888E — Maximum Subsequence

思路

cf888E — Maximum Subsequence

题意

给定 $n$ 个正整数 $a_i$ 和模数 $m$，可选任意子序列（可为空），最大化 $\big(\sum_{i\in b} a_i\big)\bmod m$。$n\le 35$，$m\le 10^9$。

思路

Meet-in-the-middle。

关键恒等式：对任意子序列和 $L,R$，有
$$(L+R)\bmod m = \big((L\bmod m)+(R\bmod m)\big)\bmod m.$$
因此可将数组拆成两半，分别 DFS 枚举子集和，入表时取 $\bmod m$（值域 $[0,m-1]$）。

设左半所有模和为集合 $A$，右半排序后为 $B$。对每个 $a\in A$：

1. 取最大 $b\in B$ 使 $a+b<m$，候选 $a+b$；
2. 再取 $B$ 中最大元素 $b_{\max}$，候选 $(a+b_{\max})\bmod m$。

因 $a,b<m$，总有 $a+b<2m$，故上述两类候选已覆盖最优（不取模时 $a+b\ge m$ 只会减一次 $m$）。

验证

• 样例 $(4,4)$：选 $\{1,2\}$，和 $7\bmod 4=3$。
• 样例 $(3,20)$：选 $\{3\}$，$299\bmod 20=19$。
• 与 $2^n$ 暴力对拍（$n\le 20$，Kali 多轮无 WA）。

复杂度

$O(2^{n/2}\log 2^{n/2})$，$n=35$ 可过。

代码

来源：problems/cf888E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:45:12
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll s[45];
vector<ll>v1,v2;
ll n,m,n1,i,j,k,ans,cur,pd;
void dfs1(ll pos,ll cur){
    if(pos>n1){
        v1.push_back(cur%m);
        return;
    }
    dfs1(pos+1,cur);
    dfs1(pos+1,cur+s[pos]);
}
void dfs2(ll pos,ll cur){
    if(pos>n){
        v2.push_back(cur%m);
        return;
    }
    dfs2(pos+1,cur);
    dfs2(pos+1,cur+s[pos]);
}
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>s[i];
    n1=n/2;
    v1.clear();
    v2.clear();
    dfs1(1,0);
    dfs2(n1+1,0);
    sort(v2.begin(),v2.end());
    ans=0;
    for(i=0;i<(ll)v1.size();i++){
        cur=v1[i];
        pd=upper_bound(v2.begin(),v2.end(),m-1-cur)-v2.begin()-1;
        if(pd>=0) ans=max(ans,cur+v2[pd]);
        ans=max(ans,(cur+v2.back())%m);
    }
    cout<<ans<<"\n";
    return 0;
}