Cod sursa(job #2278612)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 8 noiembrie 2018 12:24:44
Problema Arbori Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
#define N 100

using namespace std;

ifstream fin("arbori.in") ;
ofstream fout("arbori.out") ;

long long dp[N][N][N] , comb[2*N][2*N] ;
int n , m , k ;
long long fact = 1 ;

long long cmb(int y,int x)
{
    long long nr ;
    if ( x == 1 )
        nr = 1 ;
    else
        nr = dp[x][(k+m-1)%m][n] ;
    if ( y )
        fact = fact * (y+nr-1) / y ;
    else
        fact = 1 ;
    return fact ;
}


int main()
{
    int i , j , p ,r ;
    fin >> n >> m >> k ;
    for ( i = 1 ; i <= n ; i++ )
        dp[1][0][i] = 1;
    for ( i = 2 ; i <= n ; i++ )
    {
        dp[i][(i-1)%m][1] = 1 ;
        for ( j = 0 ; j < m ; j++ )
        {
            for ( p = 2 ; p <= n ; p++ )
            {
                for ( r = 0 ; r*p < i ; r++ )
                {
                    dp[i][j][p] += dp[i-p*r][(j-r+100*m)%m][p-1]* cmb(r,p) ;
                }
            }
        }
    }
    fout << dp[n][k][n] ;
}