Link: 一卡通大冒险
Input
包含多组数据,第一行为n,表示接下来有n组数据。以下每行一个数x,表示共有x张一卡通。(1≤x≤2000).
Output
对每组数据,输出一行:不同的方法数,因为这个数可能非常大,我们只需要它除以1000的余数。
Sample Input
4
1
2
3
100
Sample Output
1
2
5
751
Problem solving:
这道题也可以用贝尔数解决。也可以用二维dp解决。我们选择的后者。
递推公式为
dp[x][y]=1 x==y
dp[x][y]=dp[x-1][y]*y+dp[x-1][y-1] x!=y
虽然规律是很简单的,但是推出来的过程是真的坎坷。也是第一次自己推出来的。很开心!
其实这道题不用找规律也可以想起来。
如果假如说现在五张卡片,如果你想放三本书里面。那么这个总共的次数会有两个来源
。其中之一是四张卡片放在三本书里面,还有一种就是四张卡片放在两本书里面。后者想要变成三本书,新多的那张卡片必须自己放一本书,所以这是直接加上的就行。但是前面的那个就不一样了,他会有很多情况。再每种三本书的方法中,每本书都可以新放进一张卡片,也就是说这种情况下可以放的次数为dp[x-1][y]*y。两者相加,递推打表后直接输出就行。
在杭电上面64MS就过了,我觉得有点玄学,毕竟预处理的时候是O(n^2)。。。
Code:
#include <iostream>
using namespace std;
int dp[2005][2005];
int main()
{
for (int i = 1; i <= 2000; i++)
{
dp[i][1] = dp[i][i] = 1;
for (int j = 2; j < i; j++)
{
dp[i][j] = (dp[i - 1][j] * j % 1000 + dp[i - 1][j - 1] % 1000) % 1000;
}
}
int n, a;
cin >> n;
while (n--)
{
int ans = 0;
cin >> a;
for (int i = 1; i <= a; i++)
ans += dp[a][i];
cout << ans % 1000 << endl;
}
}