题解 P2028 【龙兄摘苹果】

· · 题解

！！！本题解主要讲算法，下列代码会hack掉，建议采用其他方法（如__int128这种黑科技） 看到这个题目肯定是要先抓住样例分析一波

n=4,k=2答案是：

{1}{2,3,4}；{2}{1,3,4}；{3}{1,2,4}；{4}{1,2,3}；
{1,2}{3,4}；{1,3}{2,4}；{1,4}{2,3}。

（思维敏锐的小伙伴肯定马上发现了规律）

好吧，那弱鸡的我们再看看可能和它有关系的数据量。

n=3,k=2

{1}{2,3}；{2}{1,3}；{3}{1,2}；

看到这些例子有没有发现，上面的7组数据中，有6组都跟是在这组的基础上加一个4进去

{1}{2,3,4}；{2}{1,3,4}；{3}{1,2,4}；
{1,2}{3,4}；{1,3}{2,4}；{1,4}{2,3}。

比如对于{1}{2，3}这组，在左边加个4，成了一组，右边加个4，又成了一组。

我们就能得到对于dp[i][j]来说（i表示框的数量，j表示装j个苹果）

那么dp[i][j]的一部分一定是从d[i][j-1]转换来的，怎么转换呢，就是再每组上放一个编号为j的苹果，而之前一共分成了i份，所以我们找到了第一部分

dp[i][j-1]*i;

然后，我们目标对准剩下的一组，{4}{1,2,3}我们发现：

在加入4之前，就是单纯的{1,2,3}这三组数，

所以这个也很好推导所有数据范围，可以得到另一部分是从把i-1个框内装j-1个苹果的基础上，我再单独放一个标号为i的苹果单独在一组。我们就也找到了第二部分

dp[i-1][j-1]

所以我们就找到了这样的动态转移方程（递推关系）

dp[i][j]=dp[i][j-1]*i+dp[i-1][j-1]

附代码,千万别提（chao）交(xi)，虽然用了ull但是也不能过

#include <bits/stdc++.h>
using namespace std;
unsigned long long dp[10005][1005];//i个篮子，放入j个苹果 
unsigned long long n,k,p;
unsigned long long m(unsigned long long x)
{
    return x%p;
}
int main()
{
    scanf("%llu%llu%llu",&n,&k,&p);
    for (int i=1;i<=n;i++)
        dp[1][i]=1;
    for (int i=2;i<=k;i++)//篮子数量 
        for (int  j=i;j<=n;j++)//没有篮子为空，至少i个篮子有i个苹果 
        {
            if (j==i)
                dp[i][j]=1;
            else
                dp[i][j]=m(m(m(dp[i][j-1])*m(i))+m(dp[i-1][j-1])); 
        }
    printf("%llu\n",m(dp[k][n])); 
    return 0;
 }