Cod sursa(job #792225)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 26 septembrie 2012 19:38:28
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#define NMAx 10100
#define MOD 30103
using namespace std;

int N,S,X,Y,Sol,Fact[NMAx];

int ExpLog(int A,int P) {
	
	int Sol=1;
	
	while(P) {
		
		if(P&1)
			Sol=(Sol*A)%MOD;
		A=(A*A)%MOD;
		P>>=1;
		}
	
	return Sol;
	
}
void cmmdc(int A,int B) {
	
	if(B) {
		cmmdc(B,A%B);
		
		int tmp=X;
		X=Y;
		Y=tmp-Y*(A/B);
		}
	
}
int inversMod(int A,int B) {
	
	X=1;Y=0;
	cmmdc(A,B);
	while(X<=0)
		X+=MOD;
	return X;
	
}
int C(int A,int B) {
	
	int e;
	
	e=inversMod(Fact[A-B],MOD);
	A=(Fact[A]*X)%MOD;
	e=inversMod(Fact[B],MOD);
	A=(A*X)%MOD;
	
	return A;
	
}
void Solve() {
	
	if(S==0 || N-S<2)
		return;
	
	int i;
	
	for(i=1,Fact[0]=1;i<=N;i++)
		Fact[i]=(Fact[i-1]*i)%MOD;
	
	Sol=(ExpLog(2,S)-2)%MOD;
	Sol=(Sol*C(N,N-S))%MOD;
	
}
void Citire() {
	
	ifstream in("functii.in");
	in>>N>>S;
	in.close();
	
}
void Afis() {
	
	ofstream out("functii.out");
	out<<Sol<<'\n';
	out.close();
	
}
int main() {
	
	Citire();
	Solve();
	Afis();
	
	return 0;
	
}