题意
在一张图中画圆，需要保证
-
每个圆圆心在(x)轴上，且是一个整数点
-
每个圆圆内任意一点的(x)坐标均在([0,n])
-
每个圆的半径是个整数，且不超过(5)
-
每个圆与其他任意一个圆的交点最多只能有一个
已知已经存在(k)个圆（保证初始图合法），求有多少种画法能够使得最后整张图满足上述条件
（什么也不画也是一种画法）
题解
（本题还有状压dp/记忆化搜索等解法）
由于每个圆圆心都是(x)轴上的整数点，且半径也是整数，故与(x)轴恒存在两个交点
所以可以将某个圆表示成一条线段((x,r) ightarrow[x-r,x+r])
那么限制也就变成了没有线段的顶点位于其余线段内
使用(dp[l][r][0])表示如果不画线段([l,r])代表的圆，有多少种画法
使用(dp[l][r][1])表示如果画线段([l,r])代表的圆，有多少种画法
通过已经存在的圆，再定义两个数组
(used[l][r])表示原图中已经存在线段([l,r])代表的圆
(nouse[l][r])表示不能再画线段([l,r])代表的圆
对于每个已经存在的圆((x,r))，将其转化为线段([l,r]=[x-r,x+r])
直接标记(used[l][r]=true)
再对不能画的圆的左右端点进行枚举
如果(Lin[0,l-1], Rin[l+1,r-1])或者(Lin[l+1,r-1], Rin[r+1,n])
就表示线段([L,R])代表的圆与([l,r])代表的圆有两个交点，此时标记(nouse[L,R]=true)
接下来考虑区间dp
区间长度(len=r-l)从小（(2)）枚举到大（(n)）
则对于(dp[l][r][0])，可以由左顶点在(l)的可行方案加上右顶点在(r)的可行方案转移得来，以保证所有圆与([l,r])这个大圆不冲突
据区间dp的通用方法，其中一个方案数可以直接由长度(-1)直接转移得到（这里直接转移顶点在(l)的可行方案）
所以得到(dp[l][r][0]+=dp[l][r-1][0]+dp[l][r-1][1])
此时对于顶点在(r)的可行方案，如果仍然用上述方法转移到(dp[l][r][0])，发现会在不画的情况下出现重复计数（即(dp[l][r-1][0])与(dp[l+1][r][0])不互相独立）
所以对于另一个方案数，需要通过进一步枚举计算来得到
这里我们枚举存在一个圆，左端点为(m)，右端点为(r)，又因为题目中半径限制为(5)，故枚举只需要进行至多(5)次
转移方案为(dp[l][r][0]+=dp[m][r][1] imes(dp[l][m][0]+dp[l][m][1]))
对于(dp[l][r][1])，如果在线段([l,r])能够不冲突地放置一个圆，那么(dp[l][r][1]=dp[l][r][0])成立
其后，如果原图中已经存在([l,r])的圆，那么(dp[l][r][0]=0)，表示这个圆不能不放
综上，转移方程为（以右端点开始枚举）
如果以左端点开始枚举，转移方程为
程序
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
bool used[1050][1050];
bool nouse[1050][1050];
ll dp[1050][1050][2];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,k,x,r;
cin>>n>>k;
for(int i=1;i<=k;i++)
{
cin>>x>>r;
used[x-r][x+r]=true;
for(int R=x-r+1;R<x+r;R++)
for(int L=0;L<x-r;L++)
nouse[L][R]=true;
for(int L=x-r+1;L<x+r;L++)
for(int R=x+r+1;R<=n;R++)
nouse[L][R]=true;
}
for(int i=0;i<n;i++)
dp[i][i+1][0]=1;
for(int len=2;len<=n;len++)
{
for(int l=0,r=len;r<=n;l++,r++)
{
if(nouse[l][r])
continue;
dp[l][r][0]=(dp[l+1][r][0]+dp[l+1][r][1])%mod;
for(int m=l+2;m<=min(l+10,r);m+=2)
dp[l][r][0]=(dp[l][r][0]+dp[l][m][1]*(dp[m][r][0]+dp[m][r][1]))%mod;
if((r-l)%2==0&&r-l<=10)
dp[l][r][1]=dp[l][r][0];
if(used[l][r])
dp[l][r][0]=0;
}
}
cout<<(dp[0][n][0]+dp[0][n][1])%mod<<'
';
return 0;
}