2013
11-12

# Cake Pieces and Plates

kcm1700, ntopia, suby, classic, tkwons, and their friends are having a birthday party for kcm1700. Of course, there is a very large birthday cake. They divide the birthday cake into undistinguishable pieces and put them on identical plates. kcm1700 is curious, so he wants to know how many ways there are to put m cake pieces on n plates.

In the only input line, there are two integers n, m (1 ≤ n, m ≤ 4 500), which are the number of the plates and the number of the cake pieces respectively.

If the number of ways is K, just output K mod 1000000007 because K can be very large.

3 7

8

There are 8 ways to fill 3 plates with 7 cakes, namely (0,0,7), (0,1,6), (0,2,5), (0,3,4), (1,1,5), (1,2,4), (1,3,3), (2,2,3).

import java.util.*;
import java.io.*;
public class Main{
static int dp[][]=new int[4501][4501];
public static void main(String args[]){

Scanner scan = new Scanner(new BufferedInputStream(System.in));
while(scan.hasNext()) {
int n = scan.nextInt();
int m = scan.nextInt();
System.out.println(f(n, m));
}
}

public static int f(int n ,int m ){ //m涓��瑗垮�n涓��瀛��

for(int i = 1; i <= m; i++) dp[1][i] = 1;
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
dp[i][j] = dp[i - 1][j];
if (i == j) dp[i][j]++;
if (j > i) dp[i][j] += dp[i][j - i];
if (dp[i][j] >= 1000000007) dp[i][j] -= 1000000007;
}
}
return dp[n][m];
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥

3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。