SOS dp

/* sosdp:记录子集合的一些信息 也称高维前缀和 复杂度:O(n*logn) 计算对于任意的i,f[i] = sum(a[j]),j&i==j dp[i][j]表示对于i来说,仅考虑前j位可能不同的子集合. 如果i的第j位为1,那么dp[i][j]=dp[i][j-1]+dp[i^(1<<(j-1))][j-1] 即子集合中,第j位为1和第j位为0的前j-1位相加 否则dp[i][j]=dp[i][j-1],即第j位一定只能为0 反之即可记录超集的一些信息 */ #include <iostream> using namespace std; int a[20]; int dp[1<<20][20]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; dp[a[i]][0] = a[i]; //考虑前0位仅有自己 } int cnt = 0; while( (1<<cnt) <= n ) cnt ++; //计算一共几位 for (int i = 1; i <= n; i++) { for (int j = 1; j <= cnt; j++) //考虑前j位 { if( i & (1<<(j-1)) ) dp[i][j] = dp[i][j-1] + dp[i^(1<<(j-1))][j-1]; //第j位为1,注意这边必须是j-1,第j位对应的值为(1<<j-1) else dp[i][j] = dp[i][j-1]; } } for (int i = 1; i <= n; i++) { cout << dp[i][cnt] << '\n'; } return 0; }