自动搬运

查看原文

来自洛谷，原作者为

	翼德天尊 2019-09-26 ~ 2024-03-03

搬运于2025-08-24 21:33:07，当前版本为作者最后更新于2020-03-21 17:08:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

翼德又来发题解啦！！！

拿到题目 ，一看标签 经过仔细观察后赫然发现——又是一道动规题！

闲话不多说，让我们一起先来看题目，申申题

1.n个苹果装k个篮子（毋庸置疑）
2.嫌结果太大还要再取余p
3.求方案总数（划重点）
4.数据大,一秒完成（敲黑板）

根据3,4条，我们可以得出结论：用动规！

那么，怎么动规呢？

一提到动规，像我们这种蒟蒻肯定首先想到的是状态转移方程这个烫手的山芋，所以，这道题也一样，它的状转移方程到底是什么呢？

//ans[i][j]-->每一步的结果，即选i个苹果和j个篮子时的方案总数
//i-->苹果数
//j-->篮子数
//状态转移方程为：
ans[i][j]=ans[i-1][j-1]+ans[i-1][j]*j

但是，为什么呢？

首先ans[ i ][ j ]无需解释。那么ans[ i - 1 ][ j - 1 ]和ans[ i - 1 ][ j ] * j是什么意思呢？

ans[i-1][j-1]表示若现在增加的这个苹果单独放一个篮子的方案总数；
ans[i-1][j]*j表示现在增加的这个苹果如果放在其它篮子里的方案总数，因为篮子有j个，所以*j.

如果你还没看明白，就再参考一下代码吧

#include<bits/stdc++.h>//美丽善良的万能头
using namespace std;
unsigned long long ans[10001][1001];//存每个状态的方案总数
long long n,k,p;//即苹果数，篮子数与取余数
int main(){
    cin>>n>>k>>p;//输入
    ans[1][1]=1;先赋源头值，即有一个苹果一个篮子时有一种放置方案
    for (int i=1;i<=n;i++){//苹果不断增加
        ans[i][1]=1;//如只有一个篮子就只有一个方案
		for (int j=2;j<=k;j++)//篮子不断增加
			ans[i][j]=((j%p)*(ans[i-1][j]%p)%p+(ans[i-1][j-1])%p)%p;//记得取余
    }
    printf("%lld\n",ans[n][k]);//输出
    return 0;//以好习惯撒花吧
}

好了，这道题的讲解就这么愉快地结束了，还有疑问可以在留言区留言哈，没有的话就动动你的小手点个赞吧！