codeforces 425E

题意：对于[l₁, r₁], [l_2, r₂]...[l_m, r_m]线段组成的一个集合S，我们定义f(S)为最大的不相交(没有任何公共点)线段数，现在给定n及k，n表示线段范围，即任何[li, ri]有1<=l_i<=r_i<=n,求有多少个集合使得f(S) = k。

思路：刚看到题目感觉不会，也就不多想。。

         突然问了下小胖，小胖说他做过，不难。。然后我就慢慢想了。。

         仔细想想，确实不难。。

          假设现在已经给定了一个S，那么我们怎么求f(S)?

          很显然，我们可以贪心，按照r排序，那么我们每次只要取最小r的线段，删除覆盖的，依次做完最后取到的线段肯定最多。。

          这么以来对于任意一个集合S，我们肯定可以用最小的有用线段的右端点r来表示其状态。。

          所以用f[i][j]表示最后一个有用线段右端点为i，最长有j段不相交的线段的方案数

          则递推到f[k][j+1](k>i)的状态有：

           在【i+1, k】区间内一定选了至少一条以k为右端点的线段，选法2^k-i - 1

           左端点在【1， i】右端点【i+1， k】的线段可以任意选不影响f值，有2^(k-i)*i种

           所以 f[k][j+1] += f[i][j] *(2^k-i - 1) * 2^(k-i)*i

code：

#include <bits/stdc++.h>
#define M0(x) memset(x, 0, sizeof(x))
#define M 1000000007
using namespace std;
typedef long long ll;
const int maxn = 512;
int n, m;
ll dp[512][512], p[300000];

void solve(){
     if (m == 0){
         puts("1");
         return;
     }
     M0(dp);
     dp[0][0] = 1;
     p[0] = 1;
     for (int i = 1; i <= n * n; ++i) p[i] = (p[i-1] << 1) % M;
     ll tmp;
     int c = 0;
     for (int i = 0; i < n; ++i)
         for (int j = 0; j < m; ++j) if (dp[i][j]){
              c = 0;
              for (int k = i+1; k <= n; ++k){
                    c += i;
                    tmp = dp[i][j] * (p[(k - i)]-1) % M * p[c] % M;
                    dp[k][j+1] = (dp[k][j+1] + tmp) % M;
              }
         }
     ll ans = 0;
     for (int i = 1; i <= n; ++i){
           tmp = p[(n-i) * i] * dp[i][m] % M;
           ans = (ans + tmp) % M; 
//           printf("%d : %lld
",i,  ans);
     }
     cout << ans << endl;
}

int main(){
    freopen("a.in", "r", stdin);
    while (scanf("%d%d", &n, &m) != EOF){
         solve();
    }
    return 0;
}