意甲冠军：

集S它包括了很多间隔[l,r]  和1<=l<=r<=n  f(S)个不相交的区间  问给出n和f(S)  有几种可能的S集合

思路：

dp好题  至于为啥是dp…  我仅仅能说是胖子大神教我的 - -b

定义 dp[i][j] 表示当n=i且f(S)=j时的S集合种类数  那么它能够通过dp[k][j-1]求得  j-1<=k<=i

能够这样理解转移

首先我们须要将 j-1 -> j 也就是加一个不相交的区间  [k+1,k+1] [k+1,k+2]...都能够  一共同拥有2^(i-k)-1种取法

上式-1由于不能全部这种区间全不取

为什么不是[k+2,...]的区间呢  由于我是遍历k的  k+2開始的区间在遍历到 k=k+1 的时候会算到

然后  我们能够随意取一些区间  这些区间一定和之前的相交

怎样一定相交呢  仅仅要让一端在k以内就好了  因此一共同拥有2^((i-k)*k)种取法

最后得出 dp[i][j] = sigma ( dp[k][j-1] * ( 2^(i - k) - 1 ) * ( 2^( (i - k) * k ) ) ) % mod

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define N 510

#define LL __int64

#define mod 1000000007

LL dp[N][N],f[N*N];

int n,m;

int main()

{

    int i,j,k;

    scanf("%d%d",&n,&m);

    for(i=1,f[0]=1;i<N*N;i++) f[i]=(f[i-1]<<1)%mod;

    for(i=0;i<=n;i++) dp[i][0]=1;

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=min(m,i);j++)

        {

            for(k=j-1;k<=i;k++)

            {

                dp[i][j]=(dp[i][j]+dp[k][j-1]*(f[i-k]-1)%mod*f[k*(i-k)]%mod)%mod;

            }

        }

    }

    printf("%I64d\n",dp[n][m]);

    return 0;

}