Pagini recente » Istoria paginii problema/pastila | Istoria paginii utilizator/sory1806 | Diferente pentru monthly-2012/runda-1/probleme intre reviziile 1 si 9 | Monitorul de evaluare | Cod sursa (job #3182046)
#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;
}