TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5901
  • 問題
  • P5901集合划分+
    制限 : 時間制限 : 10000 MS   メモリ制限 : 10240 KB
    問題説明

    n个元素的集合{1,2,…, n}可以划分为若干个非空子集。
    例如,当n=3时,集合{1,2,3}可以有5 个不同的非空子集。划分方案:
    3个子集,1个方案:{{1},{2},{3}}
    2个子集,3个方案:{{1,2},{3}},{{1,3},{2}},{{1},{2,3}}
    1个子集,1个方案:{{1,2,3}} 

    例如,当n=4 时,集合{1,2,3,4}可以划分为15 个不同的非空子集如下:
    {{1},{2},{3},{4}},
    {{1,2},{3},{4}},
    {{1,3},{2},{4}},
    {{1,4},{2},{3}},
    {{2,3},{1},{4}},
    {{2,4},{1},{3}},
    {{3,4},{1},{2}},
    {{1,2},{3,4}},
    {{1,3},{2,4}},
    {{1,4},{2,3}},
    {{1,2,3},{4}},
    {{1,2,4},{3}},
    {{1,3,4},{2}},
    {{2,3,4},{1}},
    {{1,2,3,4}}

    给定正整数n(1<=n<=5000),计算出n个元素的集合{1,2,...,n} 可以化为多少个不同的非空子集,模1,000,000,007。

    入力形式

    一个整数n

    出力形式

    一个整数,表示划分的方案数模1,000,000,007

    サンプル入力 1

    3

    サンプル出力 1

    5

    サンプル入力 2

    4

    サンプル出力 2

    15


    ソース  感谢nodgd