HDU 2512 一卡通大冒险(第二类stirling数)

题目链接

题目大意

  略

解题思路

  分别将n个物品放进1~n个盒子里，且不考虑盒子内的顺序，就是最经典的第二类斯特林数。

代码

const int maxn = 2e3+10;
const int maxm = 1e4+10;
int s[maxn][maxn];
int main() {     
    s[0][0] = 1;
    for (int i = 1; i<maxn; ++i)
        for (int j = 1; j<=i; ++j)
            s[i][j] = (j*s[i-1][j]%1000+s[i-1][j-1])%1000;
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        int ans = 0;
        for (int i = 1; i<=n; ++i)
            ans = (ans+s[n][i])%1000;
        cout << ans << endl;
    }
    return 0;
}