Cod sursa(job #475915)

Utilizator freak93Adrian Budau freak93 Data 9 august 2010 11:36:08
Problema Permutari2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<fstream>

using namespace std;

const char iname[]="permutari2.in";
const char oname[]="permutari2.out";
const int maxn=305;
const int mod=10007;

ifstream f(iname);
ofstream g(oname);

int dp[maxn][maxn],p,i,n,k,j,r;

int main()
{
    f>>n>>k;
    p=1;
    dp[1][1]=1;
    for(i=2;i<=n;++i)
    {
        for(j=2;j<=i;++j)
            for(r=j-1;r<i;++r)
                dp[i][j]=(dp[i][j]+dp[r][j-1]*dp[i-r][1])%mod;
        p=(p*i)%mod;;
        dp[i][1]=p;
        for(j=2;j<=i;++j)
        {
            dp[i][1]-=dp[i][j];
            if(dp[i][1]<0)
                dp[i][1]+=mod;
        }
    }
    g<<dp[n][k]<<"\n";
}