转载

UESTC_敢说就敢做 CDOJ 631

敢说就敢做

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

beap总是自诩敢说又敢做，又到了情人节，为了体现自己的勇气可嘉，beap决定给自己喜欢的女生买玫瑰花，以此表达自己的爱意。到花店里，他发现一共有 K种花，同时他从网上得知，送 N朵花的花语是LOVE，所以他决定在所有的花里面选 N朵出来送给心爱的女生，但是又为了显示自己买了那么多种花，他决定这 K种花一定要都出现在这 N朵里面。现在beap将这些花排成一排，他想知道满足条件的 N朵花，能摆成多少种形态呢？

Input

多组测试数据

每组测试数据包含两个整数 N , K( 0 < N ≤ 1000, 0 < K ≤ 30)， N代表花的朵数，

Output

对于每个 N , K，输出答案 m o d 123456781。

Sample input and output

Sample Input	Sample Output
1 1 2 2	1 2

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; }