Cod sursa(job #3182046)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 8 decembrie 2023 16:45:11
Problema Arbori Scor 70
Compilator cpp-64 Status done
Runda ce_concurs Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("arbori.in");
ofstream fout("arbori.out");
typedef long long ll;
ll n,m,k;
ll dp[105],ruk[105][105],aux[105][105],sb[105];
ll lft[105];
ll comb(ll a,ll b)
{
    if(a<b)
        return 0;
    for(ll i=1;i<=b;i++)
        lft[i]=i;
    ll ans=1;
    for(ll i=a-b+1;i<=a;i++)
    {
        ll val=i;
        for(ll j=1;j<=b;j++)
        {
            ll g=__gcd(val,lft[j]);
            val/=g;
            lft[j]/=g;
        }
        ans*=val;
    }
    return ans;
}
void build(ll last)
{
    for(ll i=1;i<=n;i++)
        sb[i]=comb(dp[last]+i-1,i);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            aux[i][j]=ruk[i][j];
    for(int cnt=0;cnt<=n;cnt++)
        for(int nodes=0;nodes<=n;nodes++)
        {
            ruk[cnt][nodes]=aux[cnt][nodes];
            for(ll take=1;take*last<=nodes&&take<=cnt;take++)
                ruk[cnt][nodes]+=aux[cnt-take][nodes-last*take]*sb[take];
        }
}
int main()
{
    fin>>n>>m>>k;
    dp[1]=1;
    ruk[0][0]=1;
    build(1);
    for(ll i=2;i<n;i++)
    {
        for(ll lg=1;lg<=i;lg++)
            if((lg+1)%m==k)
                dp[i]+=ruk[lg][i-1];
        build(i);
    }
    ll ans=0;
    for(ll lg=1;lg<=n;lg++)
        if(lg%m==k)
            ans+=ruk[lg][n-1];
    fout<<ans;
    return 0;
}