计数在网格上为方块着色的方法
Counting ways to colour squares on a grid
在做一些其他事情的时候，我遇到了以下问题：
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.
我能想到的最好的是 O(RB^2 + CB)。该方法是一个简单的 DP，其中状态是 [您正在为哪一列着色，还有多少方块要着色]，递归涉及选择您希望在此列中着色多少个方块。
这是一种使用生成函数查看此问题的方法。
用偶数个彩色方块为列着色的方法数的生成函数（多项式）是
a(x) = 1 + (R choose 2)x^2 + (R choose 4)x^4 + ...
您正在尝试计算 a(x)^C 中 x^B 的系数。您的方法是计算 a(x), a(x)^2, a(x)^3, ... 的 x^B 项，基本上是通过在每一步中乘以前几项。
通过连续平方计算 a(x)^C 应该是一种改进：计算 a(x)^2^k 直到 log_2 C 的 k 值，然后将相应的值相乘在 C 的二进制展开中为 1s。例如，如果 C=100 = 1100100_2，则计算 a(x), a(x)^2, a(x)^4, ... a(x )^64 然后
a(x)^100 = a(x)^64 * a(x)^32 * a(x)^4.
这会占用更多内存，但如果这是一个问题，您可以计算 a^1、a^2、a^3、a^6、a^12、a^24、a^25、a ^50, a^100 这样在每一步你都可以平方或乘以 a 来计算 a^（1100100_2 的前缀）。
你可以更好地使用特定形式 a(x) = ((1+x)^R + (1-x)^R)/2，比如应用二项式定理，但我没有让这个方法更快。
在做一些其他事情的时候，我遇到了以下问题：
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.
我能想到的最好的是 O(RB^2 + CB)。该方法是一个简单的 DP，其中状态是 [您正在为哪一列着色，还有多少方块要着色]，递归涉及选择您希望在此列中着色多少个方块。
这是一种使用生成函数查看此问题的方法。
用偶数个彩色方块为列着色的方法数的生成函数（多项式）是
a(x) = 1 + (R choose 2)x^2 + (R choose 4)x^4 + ...
您正在尝试计算 a(x)^C 中 x^B 的系数。您的方法是计算 a(x), a(x)^2, a(x)^3, ... 的 x^B 项，基本上是通过在每一步中乘以前几项。
通过连续平方计算 a(x)^C 应该是一种改进：计算 a(x)^2^k 直到 log_2 C 的 k 值，然后将相应的值相乘在 C 的二进制展开中为 1s。例如，如果 C=100 = 1100100_2，则计算 a(x), a(x)^2, a(x)^4, ... a(x )^64 然后
a(x)^100 = a(x)^64 * a(x)^32 * a(x)^4.
这会占用更多内存，但如果这是一个问题，您可以计算 a^1、a^2、a^3、a^6、a^12、a^24、a^25、a ^50, a^100 这样在每一步你都可以平方或乘以 a 来计算 a^（1100100_2 的前缀）。
你可以更好地使用特定形式 a(x) = ((1+x)^R + (1-x)^R)/2，比如应用二项式定理，但我没有让这个方法更快。