有点摆，整场没看A，结果考完了好像手玩了一下就会了？
A solution
还是有点智慧的计数吧，考虑 dp
发现题目要求的是安排课程的方案，并不是选课的方案，所以考虑钦定右端点方便计数
设 f[i][j] 表示安排的所有课程的最右端到达了 i 且此时最多选 j 门课
发现对于 f[i][j] 的转移好像不是很显然，为了方便转移，考虑新加一个 dp 数组 g
g[i][j] 表示安排的所有课程的最右端到了 i 且此时最多选 j 门课，且 i 这个点被选的课包含了
那么转移就很好推了
对于 f[i][j]，枚举 k，那么前 k 个点必须至少有一个点多安排一门课且这个点作为左端点，且右端点在 i，那么显然这部分就是 \(2^k-1\)，因为要减去全都不选的情况。然后包含了 i 这个点之后，前 k 个点显然现在可以对 k+1 到 i 个点进行覆盖，但是由于我们已经考虑了对于 i 的覆盖，所以是 k+1 到 i-1 这些点，这一部分就是 \(2^{k*(i-k-1)}\)
至于 g[i][j]，枚举 k，考虑其由 g[k][j-1] 转移过来。那么第 k+1 到 i 必须至少有一个点作为左端点来包含 i，这部分为 \(2^{i-k}-1\)，然后我们发现前 k 个点这时候可以随便覆盖 k+1 到 i 这些点，这样并不会影响答案，所以这部分为 \(2^{k*(i-k)}\)
至此，本题解决
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e3+10,p=1e9+7,T=2;
int f[N][N],g[N][N];
int n,m;
inline int qpow(int x,int y)
{
int ret=1;
while(y)
{
if(y&1) ret=1ll*ret*x%p;
x=1ll*x*x%p;
y>>=1;
}
return ret;
}
signed main()
{
// freopen("seg.in","r",stdin);
// freopen("seg.out","w",stdout);
cin>>n>>m;
g[0][0]=1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
for(int k=0;k<i;++k)
{
g[i][j]=(g[i][j]+(((g[k][j-1]*(qpow(T,i-k)-1))%p)*qpow(T,k*(i-k)))%p)%p;
g[i][j]=(g[i][j]+p)%p;
}
for(int k=0;k<i;++k)
{
f[i][j]=(f[i][j]+(((g[k][j]*(qpow(T,k)-1))%p)*qpow(T,k*(i-k-1)))%p)%p;
f[i][j]=(f[i][j]+p)%p;
}
f[i][j]=(f[i][j]+g[i][j])%p;
}
}
int ans=0;
for(int i=1;i<=n;++i) ans=(ans+f[i][m])%p;
cout<<ans;
return 0;
}
/*
3 9 13 18 23
*/
`