一到DP题,用递归肯定超时,建议参考
转移方程为
f[i][j] = f[i-1][j-1] + f[i-1][j] * j;
套一下应该就能过了
by Zhouw @ 2022-07-30 22:53:58
到了,记得开long long,不然也会爆
by Zhouw @ 2022-07-30 22:55:09
不好意思,打错字了,是“对了”
by Zhouw @ 2022-07-30 22:56:01
@[Jesusdalao](/user/701230)
by Zhouw @ 2022-07-30 22:57:29
@[Zhouw](/user/495068) 加个记忆化就行,好像还炸 LL,开 ULL.
by Gym_nastics @ 2022-07-31 06:25:28
给你调出来了@[Jesusdalao](/user/701230)
```cpp
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,a,b;
int j[10001][1001];
int guo(int a,int b){
if(j[a][b]) return j[a][b];
if(a==1||b==1) return 1;
if(a<b) return 0;
if(a==b) return 1;
if(a>b) return j[a][b]=(b*guo(a-1,b)+guo(a-1,b-1))%n;
}
main(){
cin>>a>>b;
cin>>n;
cout<<guo(a,b)%n<<endl;
return 0;
}
```
by Gym_nastics @ 2022-07-31 06:26:25
记忆化也行,不过正解DP
by Zhouw @ 2022-07-31 08:22:39
Orz
by Jesusdalao @ 2022-07-31 20:38:17