山東省第5回ACM大学生プログラム設計コンテストHearthstone II組合せ数学Stirling数

Hearthstone II
Time Limit: 2000MS Memory limit: 65536K
タイトルの説明
The new season has begun, you have n competitions and m well prepared decks during the new season. Each competition you could use any deck you want, but each of the decks must be used at least once. Now you wonder how many ways are there to plan the season — to decide for each competition which deck you are going to used. The number can be very huge, mod it with 10^9 + 7.
 
入力
The input file contains several test cases, one line for each case contains two integer numbers n and m (1 ≤ m ≤ n ≤ 100).
 
しゅつりょく
One line for each case, output one number — the number of ways.
サンプル入力

3 2
100 25

サンプル出力

6
354076161

ヒント
 
ソース
2014年山東省第5回ACM大学生プログラム設計コンテスト
サンプルプログラム
 
Stirling数は、ストリン数とも呼ばれ、組合せ数学では、Stirling数は2種類の数を指すことができ、第1のクラスは正負であり、その絶対値はn個の要素を含む集合をK個の配列に分ける方法の数である.第2クラスのStirling数は,n個の要素を含む集合をちょうどK個の非空子集合に分割する方法の数である.
本題の説明は、少なくとも1回使用するテーブルがないことを要求します.つまり、第2のクラスのStirling数です.そして、毎回任意のテーブルで使用できる総シナリオ数はS[N][M]*Mです.
ACcode:

#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define maxn 105
#define ll long long
const ll mod=1e9+7;
using namespace std;
ll stirling[maxn][maxn];
void init(){
    memset(stirling,0,sizeof(stirling));
    stirling[1][1]=1;
    for(ll i=2;i<=maxn;++i)
        for(ll j=1;j<=i;++j)
            stirling[i][j]=(stirling[i-1][j-1]+j*stirling[i-1][j])%mod;
}
int main(){
    int a,b;init();
    while(~scanf("%d%d",&a,&b)){
       ll ans=stirling[a][b];
       for(int i=2;i<=b;++i)ans=(ans*i)%mod;
       cout<<ans<<'\12';
    }
    return 0;
}