J. Abstract Painting（状压dp）

题意

给定n，在x轴[0,n]范围内画半径不超过5的圆，圆心在x轴上，要求任意两个圆不相交（可以相切），且已有固定的k个圆，求满足条件的画法方案数。

分析

很明显从dp的角度思考，一开始考虑区间dp，但是总状态数 O ( n 2 ) O(n^2) O(n2) ，转移 O ( n ) O(n) O(n)，总复杂度 O ( n 3 ) O(n^3) O(n3)，超时。

于是从线性dp的角度考虑，发现因为圆的半径小于等于5，因此某一点的情况只对从这一点往后10个点有后效性，也就是说可以用状态压缩的方法记录前10个点是否在某个圆内 ( 2 10 ) (2^{10}) (210)，同时枚举所有以某点为右界的圆的方案数（ 2 5 2^5 25）进行转移。状态数 O ( 2 10 ⋅ n ) O(2^{10}·n) O(210⋅n)，转移复杂度 O ( 2 5 ) O(2^5) O(25)。对于已经存在的圆，转移时要检查转移后的方案是否包含了这个圆，如果不包含则不进行转移。

代码

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'

using namespace std;
typedef long long ll;

const int N = 1e3 + 5, M = 1200, MOD = 1e9 + 7, MK = 1023;

int n, k;

ll dp[N][M];

int pos[40], mask[40];

vector<int> fix[N];

int main() { 
    cin >> n >> k;
    for (int i = 1; i <= k; i++) { 
        int c, r; scanf("%d %d", &c, &r);
        c++;
        fix[c + r].push_back(r * 2);
    }
    memset(mask, -1, sizeof(mask));
    for (int i = 1; i <= 31; i++) { 
        int tmp = 0;
        for (int j = 4; j >= 0; j--) { 
            tmp = (tmp * 2 + ((i >> j) & 1)) * 2;
            if (mask[i] == -1 && ((i >> j) & 1)) mask[i] = (1 << (j * 2 + 1)) - 1;
        }
        pos[i] = tmp;
    }
    dp[0][MK] = 1;
    for (int i = 0; i <= n; i++) { 
        for (int j = 0; j <= MK; j++) { 
            if (fix[i + 1].size() == 0) { 
                dp[i + 1][(j << 1) & MK] += dp[i][j];
                dp[i + 1][(j << 1) & MK] %= MOD;
            }
            for (int k = 1; k <= 31; k++) { 
                bool cont = 0;
                for (int to : fix[i + 1]) { 
                    if (!((pos[k] >> (to - 1)) & 1)) cont = 1;
                    if (cont) break;
                }
                if (cont || (j & pos[k]) != 0) continue;
                dp[i + 1][(((j | mask[k]) << 1)) & MK] += dp[i][j];
                dp[i + 1][(((j | mask[k]) << 1)) & MK] %= MOD;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i <= MK; i++) { 
        ans += dp[n + 1][i];
        ans %= MOD;
    }
    cout << ans;
    return 0;
}