题目描述 你面临一个简单任务。

给 n个物品，第 i 个物品价值 a[i]，挑出其中一个子集，使子集中物品价值之和在 mod p modp 意义下最大。

输入格式 第一行 2 2 个整数 n,p。

第二行 n 个非负整数 a[i]。

输出格式 输出 1 1 个整数，代表 mod p modp 下能得到的最大子集价值。

样例 #1 样例输入 #1 4 4 5 2 4 1

样例输出 #1 3 样例输入 #2 5 233 123 456 789 12 15

样例输出 #2 230 提示 对于测试点 1 − 2 1-2： ≤ 2 0 n≤20， ≤ 1 0 0 p≤100

对于测试点 3 − 5 3−5： ≤ 1 0 0 n≤100， ≤ 2 × 1 0 5 p≤2×10 5

对于测试点 6 − 7 6−7： ≤ 2 5 n≤25， ≤ 1 0 9 p≤10 e 9 对于测试点 8 − 1 0 8−10： ≤ 3 6 n≤36， ≤ 1 0e 9 p≤109对于 100% 的数据：≤100n≤100, ,≤10e9 a[i],p≤10e9 ，特别注意本题 8−10 测试点的 n 范围并不是最大的。 状压代码（本来是想用动态规划的）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ls[100050];
int main()
{
    ll n,p,ans=INT_MIN;
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>ls[i];
    for(int i=0;i<(1<<n);i++)
    {
        ll s=0;
        for(int j=0;j<n;j++) s=(s+ls[j+1]*((i&(1<<j))>>j))%p;
        //cout<<s<<endl;
        ans=max(ans,s);
    }
    cout<<ans;
    return 0;
}

本来用状压是想拿40-70分的，结果才20分，求调，顺便帮忙想一下动态规划正解