Cod sursa(job #526097)

Utilizator S7012MYPetru Trimbitas S7012MY Data 27 ianuarie 2011 13:20:47
Problema Generare de permutari Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define REST 41143
#define DK 200
using namespace std;

typedef int mat22[DK][DK];

mat22 mi,rezultat,mu;
int n,k,c[DK][DK];

void matun() {
	for(int i=0; i<=k; i++)
		mu[i][i]=1;
}


void inmultire(mat22 a, mat22 b, mat22 c) {
    for(int i=0;i<=k; ++i) for(int j=0; j<=k; ++j) {
        int s=0;
        for(int l=0;l<=k; ++l) s=(s+a[i][k]*b[k][j])%REST;
        c[i][j]=s;
    }
}

void putere(long long k, mat22 a) {
	long long exponent=k;
	int lt=sizeof(mat22);
	mat22 baza,rez,rez2;
	memcpy(rezultat,mu,lt);
	memcpy(baza,a,lt);
	while(exponent>0) {
		while(!(exponent%2)) {
			inmultire(baza,baza,rez);
			memcpy(baza,rez,lt);
			exponent>>=1;
		}
		exponent--;
		inmultire(rezultat,baza,rez2);
		memcpy(rezultat,rez2,lt);
	}
}

int v[DK],vr[DK];

void inmultirev() {
	for(int i=0; i<=k; ++i) {
		vr[i]=0;
		for(int j=0; j<=k; ++j)
			vr[i]=(vr[i]+(rezultat[i][j]*v[j])%REST)%REST;
	}
}

int main()
{
    ifstream f("pkinv.in");
    ofstream g("pkinv.out");
    //f>>n>>k;
    cin>>n>>k;
    for(int i=1; i<=n; ++i) c[i][0]=1;
    for(int i=2;i<=n; ++i) for(int j=1; j<=k; ++j) {
        int s=0;
        for(int l=max(j-i+1,0);l<=j;++l) s=(s+c[i-1][l])%REST;
        c[i][j]=s;
    }
   // for(int i=0; i<=k; ++i) for(int j=i; j<=k; ++j) mi[i][j]=1;
   // matun();
   // putere(n-k-1,mi);
   // for(int i=0; i<=k;++i) v[i]=c[k+1][i];
   // inmultirev();
   // g<<vr[k];
    cout<<c[n][k];
    return 0;
}