题解NC51165自然数拆分Lunatic版

因为 ，暴搜肯定会超时，所以我采用了分治和记忆化思想来解。

其他都好理解……

上Mr.Code!

#include <bits/stdc++.h>
#define mod 19930125
using namespace std;
int f[5001][5001];
int dec(int l,int r)
{
    if (r>l) r=l;
    if (f[l][r]!=0) return f[l][r];
    if (l==0 || l==1 || r==1) return 1;
    return f[l][r]=(dec(l-r,r)+dec(l,r-1))%mod;
}
int main()
{
    //分解自然数
    int n;
    scanf("%d",&n);
    printf("%d",((dec(n,n)-1)%mod+mod)%mod);
}