HDU 2512 一卡通大冒险

我感觉这更像个数学问题。

dp[i][j]表示将i件物品分成j组的方案数。

状态转移方程：

dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];

将i张卡分成j组可以有之前两种情况得来：i-1张卡分成j-1组，只要将第i张卡独立分成一组就行了，或者是i-1张卡分成j组，第i张卡随便插入哪一组都符合条件。

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 int dp[maxn][maxn];

 int main(void)

 {

     #ifdef LOCAL

         freopen("2512in.txt", "r", stdin);

     #endif

     int i, j;

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

     {

         dp[i][] = ;

         dp[i][i] = ;

     }

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

         for(j = ; j < i; ++j)

             dp[i][j] = (dp[i-][j-] + j * dp[i-][j]) % ;

     int n, num, sum;

     scanf("%d", &n);

     while(n--)

     {

         scanf("%d", &num);

         sum = ;

         for(i = ; i <= num; ++i)

             sum = (sum + dp[num][i]) % ;

         printf("%d\n", sum);

     }

     return ;

 }

代码君