TopCoder SRM 848 AlternateParity.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>


using namespace std;


const int MODULE = 1000000007;
const size_t MAX_N = 100000;
class Combo {
    
    long long fac[MAX_N+10];

    long long pow_mod(int base, int index) {
        
        if (index == 0) {
            return 1;
        }
        if (index == 1) {
            return base;
        }
        int half_index = index / 2;
        long long half_ans = pow_mod(base, half_index);
        long long ans = half_ans * half_ans % MODULE;
        if (index % 2 != 0) {
            ans = ans * base % MODULE;
        }
        return ans;
        
        
    }
    public:
     Combo() {
        fac[1] = 1;
        for (size_t i=2; i<MAX_N; ++i) {
            fac[i] = fac[i-1] * i % MODULE;
        }

    }
    public:
     long long choose(int n, int r) {
         if (n < r) {
                // debug only
                return -1;
         }
         if (n < 1 || r < 1) {
             //debug
             return -2;
         }
        if (n == r) {
            return 1;
        }
        long long ans = fac[n] * pow_mod(fac[n-r], MODULE-2) % MODULE
            * pow_mod(fac[r], MODULE-2) % MODULE;
        return ans;
    }
};
class AlternateParity {
public:

	int count(int N, int L) {
        Combo combo;
        /*
        for (int n=1; n<=10; ++n) {
            cerr<<"n= " << n << " : ";
            for (int r=1; r<=10; ++r) {
                //cerr << " (n, r) " << n << " , " << r << endl;
                cerr << combo.choose(n, r) << ", ";
            }
            cerr << endl;
        }
        */
        
        long long ans = 0;
        for (int X = L; X <= N; ++X) {
            bool same_parity = (X + L) % 2 == 0;
            int sum_c;
            if (same_parity) {
                sum_c = (X+L) / 2;
            } else {
                sum_c = (X+L-1) / 2;
            }
            long long tmp_ans = combo.choose(sum_c-1, L-1);
            //fprintf(stderr, "f(%d,%d)=%lld\n", L, X, tmp_ans);
            ans += tmp_ans;
            ans %= MODULE;
        }
        
        return ans;
	}
};


// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
bool KawigiEdit_RunTest(int testNum, int p0, int p1, bool hasAnswer, int p2) {
	cerr << "Test " << testNum << ": [" << p0 << "," << p1;
	cerr << "]" << endl;
	AlternateParity *obj;
	int answer;
	obj = new AlternateParity();
	clock_t startTime = clock();
    cerr << "Before test " << endl;
	answer = obj->count(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cerr << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cerr << "Desired answer:" << endl;
		cerr << "\t" << p2 << endl;
	}
	cerr << "Your answer:" << endl;
	cerr << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	if (!res) {
		cerr << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cerr << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cerr << "Match :-)" << endl;
	} else {
		cerr << "OK, but is it right?" << endl;
	}
	cerr << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	int p0;
	int p1;
	int p2;
	
	{
	// ----- test 0 -----
	p0 = 6;
	p1 = 6;
	p2 = 1;
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	p0 = 5;
	p1 = 2;
	p2 = 6;
	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	p0 = 12;
	p1 = 4;
	p2 = 105;
	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cerr << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cerr << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// END KAWIGIEDIT TESTING
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!