Codeforces449D - Jzzhu and Numbers - 배제, 상압 dp

D. Jzzhu and Numbers
제목: 수열 a 1, a 2,... & Thin Space;a n a_1,a_2,\cdots, a_na1, a2,..., an, ai 1 & ai 2 & & & ai k = 0 a{i_1}\\&\a_{i_2}\\&\\cdots\\&\a_{i k}=0 ai1 & ai2 &... & aik=0, 답안 추출 모드 1 0 9+7 10^9+7 109+7.

1 ≤ n ≤ 1 0 6 1\le n\le 10^6 1≤n≤106

0 ≤ a i ≤ 1 0 6 0\le a_i\le 10^6 0≤ai​≤106

문제풀이: 아주 아름다운 용척해법.2진법으로 이 문제를 고려하여 f[i] f[i] f[i]는 하위 서열을 취하여 조작 후 적어도 ii개 111의 방안 수를 표시한다. 그러면 답은 fff를 용납한 결과(f[0]--f[1]+f[2]---+f[20] f[0]-f[1]+f[2]-\cdots+f[20] f[0]-f[20] f[2]-\f[2]-f]-f[20] f[2]-f[2]-f]-f[2]-f[2]-f[1]-f[2]-f[2]+f[2]그리고 어떻게 fff를 구하는지 생각해봐.g[s] g[s] g[s]를 설정하면 하위 서열을 추출하여 작업 후 최소한 ss의 정수 ai 를 포함하도록 합니다iai개수(g[s] g[s] g[s] g[s]가 nn을 초과하지 않는다는 것을 알아차리면) 각 g[s] g[s] g[s]에 대해 상태 ss에 ii i개 1 1 1이 있다고 가정하면 f[i] f[i] f[i] f[i] f[i]에 기여해야 한다. 아무리 ss의 서열을 가져와도 그것들을 조작한 후에 적어도 ii i개 1 1 1이 있으면 그 공헌이 비어있는 서브집합 숫자가 아니라는 것을 쉽게 알 수 있다.즉 2g[s]--12^{g[s]}-12g[s]--1.다음 문제는 어떻게 g[s]g[s]g[s]를 구하는가가 되었다.이것은 사실 고전적인 동적 기획 문제이다. g[s]=∑t&s=sg[t]g[s]=\sum\limits{t\&s=s}g[t]g[s]=t&s=s∑g[t], 구체적인 방법은 위치별로 이동하여 순서대로 sss에서 s⊕2 is\oplus2^i s⊕2i로 옮기면 O(20⋅max {a i}) O(20\cdot\texttt {max} {a i\}) O(20⋅max {ai})는 무겁지 않고 계산할 수 있다.
물론 g[s] g[s] g[s] g[s]를 계산하면 gg를 직접 용납해도 답을 얻을 수 있다. 즉, g[s] g[s] g[s] 중 ss의 111의 개수를 토론하고 플러스와 마이너스를 토론하는데 이것은 상기 방법의 등가와 같다.
코드:

#include 
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int max_n = 1e6 + 5;
int dp[max_n];
ll f[21], b[max_n];
int main() {
    int n;
    scanf("%d", &n);
    memset(dp, 0, sizeof dp);
    int mx = 0;
    b[0] = 1;
    for (int i = 1; i <= n; i++) b[i] = (b[i-1] << 1) % mod;
    for (int i = 1; i <= n; i++) {
        int a_i;
        scanf("%d", &a_i);
        mx = max(mx, a_i);
        dp[a_i]++;
    }
    for (int j = 0; j <= 20; j++) {
        for (int i = 1; i <= mx; i++) if (dp[i]) {
            if (i & (1 << j)) {
                dp[i^(1<