敢说就敢做
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
beap总是自诩敢说又敢做，又到了情人节，为了体现自己的勇气可嘉，beap决定给自己喜欢的女生买玫瑰花，以此表达自己的爱意。到花店里，他发现一共有K种花，同时他从网上得知，送N朵花的花语是LOVE，所以他决定在所有的花里面选N朵出来送给心爱的女生，但是又为了显示自己买了那么多种花，他决定这K种花一定要都出现在这N朵里面。现在beap将这些花排成一排，他想知道满足条件的N朵花，能摆成多少种形态呢？
Input
多组测试数据
每组测试数据包含两个整数N,K(0<N≤1000, 0<K≤30)，N代表花的朵数，K代表花的种类数。
Output
对于每个N,K，输出答案mod 123456781。
Sample input and output
| Sample Input | Sample Output |
|---|---|
1 1 |
1 |
Source
2012 UESTC ACM-ICPC Summer Training Team Selection 4
解题报告：
这是一道组合数学题目.
我么首先容易想到的是这样的思路： A(N,K) * k ^ ( n- k ) ,即，先给K朵花安置好，然后剩下的位置，每个都有K种选择，即K^( n - k )
但是这样是错误的，因为有重复的情况（仔细想想）.
既然这条路走不通，我们只能尝试从一朵一朵花上递推进行入手了
令 DP ( i , j ) 表示还有 i 个位置，已经放置好了第 1 种 到第 j 种花的方案数
（想一想为什么是还有 i 个位置，而不是已经放好了第 1 个到 i 个位置呢）
转移：
k start from 1 to i - j + 1 (include)
DP(i,j) += DP(i-k,j-1) * C(i,k)
我们考虑这个方程，因为每朵花至少要有一个，我们K自然而然的从 1 开始，那么为什么结束条件是 i - j +１ 呢，因为还有ｊ－１种花，每种至少要一朵，我们要给他们预留位置，之后乘上C( i ,k)就很好理解了，选位置，同时同种花之间没有区别
边界条件:
if (j == 0 )
{
if (i == 0 ) return 1;
else return 0;
}
显然必须要把位置放满才能是合法的
这样，就解决了本题
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <string>
#include <ctime>
typedef unsigned char byte;
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.txt","r",stdin) using namespace std;
const int maxn = 1e3 + 50;
const long long mod = 123456781;
long long kp[maxn][maxn];
long long dp[maxn][35]; long long counter(int x,int y)
{
if (kp[x][y] != -1)
return kp[x][y];
long long & ans = kp[x][y];
if (x == y || y == 0) return ans = 1;
return ans = (counter(x-1,y-1) + counter(x-1,y) ) % mod;
} long long dfs(int x,int y)
{
if (dp[x][y] != -1)
return dp[x][y];
long long & ans = dp[x][y] = 0;
if (y == 0) return (ans = (x==0));
for(int i = 1 ; i <= x - y + 1 ; ++ i)
{
ans += counter(x,i) * dfs(x - i , y - 1);
if (ans >= mod)
ans %= mod;
}
return ans;
} int main(int argc,char *argv[])
{
int n , k ;
memset(dp , -1 , sizeof(dp));
memset(kp , -1 , sizeof(kp));
while(~scanf("%d%d",&n,&k))
{
if (n < k) printf("0\n");
else
printf("%lld\n",dfs(n,k));
}
return 0;
}