hdu 4472 Count （2012 ACM-ICPC 成都现场赛）

递推，考虑到一n可以由i * j + 1组合出来，即第二层有j个含有i个元素的子树。。。然后就可以了。。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<fstream>

#include<sstream>

#include<bitset>

#include<vector>

#include<string>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define debug puts("**debug**")

#define LL long long

#define PB push_back

#define SL(a) strlen(a)

using namespace std;

const int N = 1111;

const int MOD = 1e9 + 7;

LL ans[N];

int main()

{

    int n, cas = 1, i, j;

    CLR(ans, 0);

    ans[1] = 1;

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

    {

        for(j = 1; i * j + 1 < N; j ++)

        {

            ans[j * i + 1] += ans[i];

            ans[j * i + 1] %= MOD;

        }

    }

    while(cin >> n)

    {

        cout << "Case " << cas ++ << ": ";

        cout << ans[n] << endl;

    }

}