题意:
给定n，在x轴[0,n]范围内画半径不超过5的圆，圆心在x轴上，要求任意两个圆不相交（可以相切），且已有固定的k个圆，求满足条件的画法方案数。
题解:
先不管已存在的圆考虑从左往右dp，dp[i]表示以i为右边界的方案数，显然从dp[i-1]到dp[i]的转移只和以i为右边界的圆有关，而圆的直径最大只有10，因此只需要知道左边10个点的状态就可以判断是否可以画圆。如果一个点在已经存在的圆的中间（不包括边界），那么这个点就不能作为以i为右边界圆的左边界，存状态只需要记录这些点是否可以作为左边界，而显然点i-1是可以作为左边界的，因为之前最大的点就是i-1，实际上只要记录每个点左边的9个点的状态就够了。
由于圆的半径有5种，因此以i为右边界画圆有(2^5)种情况，即每种状态有(2^5)种转移方式，状态数有(2^9*n)个，复杂度为(O(2^{14}*n))是可行的
对于已有的圆，在枚举点i作为右边界时，只要判断i周围+-10格范围内的圆造成的影响即可：
- 如果i在一个圆内部，则不能以这个圆外部的点作为左边界
- 如果i在一个圆外部，则不能以这个圆内部的点作为左边界
- 如果i在一个圆的右边界，则不能以这个圆的左边界作为左边界
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=2e3+5;
const int maxs=(1<<9)+1;
const int b9=(1<<9)-1;
int dp[maxn][maxs];
int b[maxn][6];
int nt[maxn];
int p,pre,Left;
inline int f(int n){//高位为1，低n位为0
int ans=(1<<30)-1;
int temp=(1<<n)-1;
return ans^temp;
}
void dfs(int r,int mx){//r:枚举到的圆半径 mx:和已画的最大圆直径
if(r==6){
int temp=mx==0?Left:Left&f(mx-1);//加上新增加圆后的状态
dp[p][temp&b9]+=dp[p-1][pre];
dp[p][temp&b9]%=mod;
return;
}
int d=r+r;
if((p-d>=0)&&((1<<(d-1))&Left)&&(!nt[p-d]&&!nt[p])){
dfs(r+1,d);
}
dfs(r+1,mx);
}
int main () {
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++){
int c,r;
scanf("%d%d",&c,&r);
b[c+r][r]=1;
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=max(0,i-11);j<=i;j++) nt[j]=0;
for(int j=max(0,i-11);j<=min(n,i+11);j++){
for(int r=1;r<=5;r++){
if(b[j][r]){
if(i<=j-r-r)//border
continue;
else if(i==j){//border
nt[j-r-r]=1;
}
else if(j-r-r<i && i<j){//in
for(int k=max(0,i-11);k<j-r-r;k++){
nt[k]=1;
}
}
else{//out
for(int k=j-r-r+1;k<j;k++){
nt[k]=1;
}
}
}
}
}
for(int st=0;st<(1<<9);st++){
if(!dp[i-1][st])continue;
p=i,pre=st,Left=st<<1|1;
dfs(1,0);
}
}
int ans=0;
for(int st=0;st<(1<<9);st++){
ans=(ans+dp[n][st])%mod;
}
printf("%d
",ans);
}