Cod sursa(job #2320967)

Utilizator armigheGheorghe Liviu Armand armighe Data 15 ianuarie 2019 14:57:36
Problema Permutari2 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<cstdio>
#include<fstream>
#define MOD 10007
using namespace std;
FILE *f=fopen("permutari2.in","r");
ofstream g("permutari2.out");
int dp[302][302],in[302];

inline void poate_merge_cu_inline()
{
    int n,k,i,j,l;
    fscanf(f,"%d%d",&n,&k);
    dp[1][1]=1;
    dp[2][1]=1;
    dp[2][2]=1;
    in[1]=1;
    for(i=2;i<=n;i++)
        in[i]=in[i-1]*i,in[i]%=MOD;
    for(i=3;i<=n;i++)
    {
        dp[i][1]=in[i];
        for(j=2;j<=i;j++)
        {
            for(l=j-1;l<i;l++)
            {
                dp[i][j]+=dp[l][j-1]*dp[i-l][1];
                dp[i][j]%=MOD;
            }
            dp[i][1]-=dp[i][j];
            if(dp[i][1]<0)
                dp[i][1]+=MOD;
        }
    }
    g<<dp[n][k];
}

int main()
{
    poate_merge_cu_inline();
    return 0;
}