题解 P2028 【龙兄摘苹果】

· · 题解

这道题初看蛮简单的，然后被卡int QwQ

思路嘛，不难想(虽然还是被卡了）
考虑f[i][j]表示i个苹果放在j个盘里面
然后呢，最后一个苹果可以独立成一个即f[i-1][j-1]
也可以是放在已经放好的盘子里面，由于说每一个苹果都是不一样的，所以还要乘上盘子的个数
所以转移方程为 *f[i][j] = f[i-1][j-1] + f[i-1][j] j**;
记得初始化跟每步取余就可以AC啦
代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
typedef unsigned long long ll;
ll f[maxn][1010];
int main()
{
    int n=0,k=0;
    ll p=0;
    scanf("%i%i%llu",&n,&k,&p);
   for(register int i=1;i<=n;i++) f[i][1]=(ll)1%p;
    for(register int i=2;i<=n;i++)
       for(register int j=2;j<=k;j++)
          f[i][j] = ((f[i-1][j-1]%p)+ (f[i-1][j]%p)*(j%p))%p ;
    printf("%llu",f[n][k]);
    return 0;
}

ull是最后的倔强