1067 - Combinations

1067 - Combinations

Topic: Counting.

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const ll Mod = 1000003;
	const ll Max = 1000005;
	ll factorial[Max];
	ll BigMod(ll N, ll POW, ll Mod)
	{
	if(POW == 0)return 1;
	if(POW&1)return ((N%Mod) * BigMod(N, POW - 1, Mod)) % Mod;
	else{
	ll d = BigMod(N, POW/2, Mod);
	return ((d%Mod) * (d%Mod)) % Mod;
	}
	}
	void fact()
	{
	factorial[0] = 1;
	factorial[1] = 1;
	for(ll i = 2; i < Max; i++){
	factorial[i] = (i*factorial[i-1]) % Mod;
	}
	}
	int main()
	{
	fact();
	int T;
	scanf("%d", &T);
	for(int cs = 1; cs <= T; cs++){
	int n,r;
	//cin >> n >> r;
	scanf("%d %d", &n,&r);
	ll res = ((factorial[n-r]) * (factorial[r]) ) %Mod;
	//cout << "Case "<<cs<<": ";
	printf("Case %d: ",cs);
	// cout << (factorial[n] * BigMod(res, Mod-2, Mod) % Mod)<<endl;
	printf("%d\n", (factorial[n] * BigMod(res, Mod-2, Mod) % Mod));
	}
	return 0;
	}

view raw 1067.cpp hosted with ❤ by GitHub

Share: