Cod sursa(job #2282488)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 13 noiembrie 2018 20:16:07
Problema Sortari2 Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <bits/stdc++.h>
#define N 1005
#define MOD 999017
using namespace std;

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

long long int dp[N][N] , fact , c[N] , sol[N] ;

int main()
{
    int n , i , j ;
    fin >> n ;
    fact = 1 ;
    for ( i = 2 ; i <= n ; i++ )
        fact = (fact*i)%MOD ;
    c[1] = 1;
    c[2] = 1 ;
    for ( i = 3 ; i <= n ; i++ )
        c[i] = (c[i-1]*2)%MOD ;
    sol[0] = 1 ;
    for ( i = 1 ; i <= n ; i++ )
        for ( j = 1 ; j <= i ; j++ )
            sol[i] = (sol[i] + sol[i-j]*c[j])%MOD ;
    fact = fact-sol[n] ;
    fout << fact;
}