Cod sursa(job #2629418)

Utilizator loraclorac lorac lorac Data 20 iunie 2020 16:58:53
Problema Arbori Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
using namespace std;
ifstream cin("arbori.in");
ofstream cout("arbori.out");
typedef long long ll;
ll n,m,k,ans;
ll sum[100];
ll aux[100][100];
ll dp[100][100];
ll tot[100];
int main()
{
    cin>>n>>m>>k;
    tot[1]=1;
    dp[1][0]=1;
    for(ll maxx=1;maxx<=n;++maxx)
        aux[1][maxx]=maxx,sum[maxx]=maxx;
    for(ll nr=2;nr<=n;++nr)
    {
        for(ll maxx=1;maxx<=n;++maxx)
            aux[nr][maxx]=sum[maxx];
        for(ll maxx=1;maxx<=n;++maxx)
        {
            sum[maxx]=sum[maxx-1]+aux[nr][maxx];
            aux[nr][maxx]=sum[maxx];
        }
    }
    for(ll subg=1;subg<n;++subg)
    for(ll card=n;card>=1;--card)
    for(ll app=n;app>=1;--app)
    for(ll buc=1;subg*buc<=card and buc<=app;++buc)
    {
        dp[card][app]+=dp[card-subg*buc][app-buc]*aux[buc][tot[subg]];
        if((app+1)%m==k) tot[card]+=dp[card-subg*buc][app-buc]*aux[buc][tot[subg]];
    }
    if(k==0) k=m;
    for(ll i=k;i<n;i+=m)
        ans+=dp[n][i];
    cout<<ans<<'\n';
    return 0;
}