敢说就敢做

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

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;

}