While doing some other things, I've come across the following problem:
There is a grid of R rows and C columns. Count the number of ways to colour B of these squares so that every column has an even number of coloured squares. Output the answer modulo 10^9+7. You may assume B is even and R >= B.
The best I've been able to come up with is O(RB^2 + CB). The approach is a simple DP where the state is [Which column you are colouring, How many squares left to colour] and the recursion involves picking how many squares you'd like to colour in this column.
Best How To :
Here is a way to look at this using generating functions.
The generating function (polynomial) for the number of ways to color a column with an even number of colored squares is
a(x) = 1 + (R choose 2)x^2 + (R choose 4)x^4 + ...
You are trying to compute the coefficient of x^B in a(x)^C. Your method is to compute the terms up to x^B of a(x), a(x)^2, a(x)^3, ... basically by multiplying out the first few terms at each step.
It should be an improvement to compute a(x)^C by successive squaring: Compute a(x)^2^k for the values of k up to log_2 C, then multiply together those corresponding to 1s in the binary expansion of C. For example, if C=100 = 1100100_2, then compute a(x), a(x)^2, a(x)^4, ... a(x)^64 and then
a(x)^100 = a(x)^64 * a(x)^32 * a(x)^4.
This uses a little more memory, but if that is an issue you can compute a^1, a^2, a^3, a^6, a^12, a^24, a^25, a^50, a^100 so that at each step you square or multiply by a to compute a^(prefix of 1100100_2).
You may be able to better using the specific form a(x) = ((1+x)^R + (1-x)^R)/2, say by applying the binomial theorem, but I haven't gotten this method to be faster.