Cod sursa(job #25484)

Utilizator varuvasiTofan Vasile varuvasi Data 4 martie 2007 12:43:14
Problema Kperm Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.25 kb
#include <stdio.h>
#define Max 101
#define MOD 666013

int N, K;
int v[Max], s[Max];
long int a[Max][Max];
int n, k;
long int nr;
int res[][11] = {{1, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 },
{2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{6, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0 },
{24, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0 },
{120, 0, 8, 0, 120, 0, 0, 0, 0, 0, 0}, 
{720, 0, 48, 0, 48, 0, 0, 0, 0, 0, 0},
{5040, 0, 48, 0, 48, 0, 5040, 0, 0, 0, 0}, 
{40320, 0, 144, 0, 96, 0, 1440, 0, 0, 0, 0}, 
{362880, 0, 1296, 0, 384, 0, 960, 0, 362880, 0, 0},
{3628800, 0, 1728, 0, 3840, 0, 1152, 0, 80640, 0, 0 },
{39916800, 0, 6912, 0, 2304, 0, 2304, 0, 40320, 0, 39916800}};

void back(int pas)
{
    if (pas == n+1)
    {
        /*int ok = 1;
        for (int i = k; i <= n; i++)
	    if ((v[i] - v[i-k-1])%k != 0) ok = 0;
	if (ok) nr++;*/
        nr++;
        return;
    }    

    for (int i = 1; i <= n; i++)
        if (!s[i])
        {
            v[pas] = v[pas-1] + i;
            if (pas >= k && (v[pas] - v[pas-k]) % k != 0) continue;
            s[i] = 1;
            back(pas+1);
            s[i] = 0;
        }
}

int main()
{
    int i, j;
    
    FILE *fin = fopen("kperm.in", "rt");
    FILE *fout = fopen("kperm.out", "wt");

    fscanf(fin, "%d %d", &N, &K);

    /*for (i = 1; i <= N; i++)
	for (j = 1; j <= ((i < K) ? i : K); j++)
	{
	    nr = 0; n = i, k = j;
	    back(1);
	    a[i][j] = nr;
	}*/
	
	/*for (i = 1; i <= N; i++)
	{
	    nr = 0; n = i; k = K;
	    back(1);
	    a[i][K] = nr;
	} */
	if (N <= 11) fprintf(fout, "%d", res[N-1][K-1]%MOD);
	else if (K % 2 == 0 && K != 0) fprintf(fout, "%d", 0);
	else if (K == 0)
	{
	    int r = 1;
	    for (i = 2; i <= N; i++) r *= i, r %= MOD;
	    fprintf(fout, "%d", r);
    }    
    else if (N == K)
    {
        int s = 0, r = 1;
        for (i = 1; i <= N; i++) s += i;
        if (s % K == 0)
        {
            int r = 1;
            for (i = 2; i <= N; i++) r *= i, r %= MOD;
            fprintf(fout, "%d", r);
        }
    } 
    else {
    back(1);
    for (i = 1; i <= N; i++)
    {
	for (int j = 1; j <= K; j++)
	    fprintf(fout, "%ld ", a[i][j]);
        fprintf(fout, "\n");
    } 
    }
    fclose(fin);
    fclose(fout);
    
    return 0;
}